When I first played when minecraft was in Alpha I got ~60 on my netbook and ~120 on my laptop. NOW I get ~20 on my Laptop.
I think they should make "Minecraft Lite" which would basically just be Alpha but with some of the new functions and blocks (new half-slabs, inverting half-slabs, sideways logs...).
I don't think you should trust the Minecraft FPS numbers when you start getting above 300-400 FPS. Then you should use a tool like Fraps instead.
Minecraft has a video option for performance that can influence FPS and I think the default value is Balanced. With that I get about 180 FPS (Fraps). If I change performance to fast it increases a lot, but it depends a great deal on what I do and where I am in Minecraft. A Jungle is very different from a small cave.
Other things to take into consideration are; your screen resolution, number of monitors, windowed mode, software running in the background. I often have youtube showing me an episode of MindCrack in full screen on my second monitor at 30 fps and that is bound to affect the FPS I get in Minecraft.