I only have a small number of players (8 in total, usually 3-4 max at one time), so this might be a factor.
I had this issue on my server (hosted externally) when the allocated RAM was low (512MB).
Increasing it to 1024MB appears to have resolved the issue for me.
Note that view-distance has always been set to 8 in the server.properties config.
It's an i7 with 8Gig RAM and a Intel HD graphics card.
Playing single player, 60FPS is the highest I get - usually around 30-40 during play.
Yes, I play with Fancy graphics and smooth lighting.
I have this issue in 1.7.4 on my multiplayer server running on Normal difficulty.
We can stay out all night and see only a few mobs (or none at all some nights).
If I download the world and play it on my local machine, I see mobs spawning almost instantly during night time (as expected).
This is a new world, created in 1.7.4.
(low mob rates is making it very hard to gather certain resources (slime balls, enderpearls etc)
I generated a new world in the final 1.8 release and all the torches in the stronghold that should have attached to blocks were sitting on the floor as items (not attached), so the issue still exists in the 1.8 release.
For what it's worth, having no torches in the stronghold made it a bit more interesting 🙂