Minecraft FPS irregular in fullscreen, but reporting 35-45

How to reproduce:

1. Start the PC, and log in to Linux Mint 12 (although I'm pretty sure the same issue appeared on Ubuntu 11.10 as well)
2. Start Minecraft
3. Maximise the window
4. Have smooth experience at 35-45 FPS
5. Quit Minecraft
6. Start Minecraft again
7. Maximise the window

At this point I'd expect Minecraft to behave in the same way as before, but there's an important difference: Most of the time (but not all of the time) when starting Minecraft the second and subsequent times after logging in, even the title screen will be choppy, looking like a movie player dropping frames all the time. The tilted text on the main screen doesn't bounce smoothly, the background doesn't pan smoothly, and the game doesn't play smoothly. The last bit is the most puzzling: It still reports 35-45 FPS, but it's clearly not displaying at that rate. Also, it still seems as smooth as before if I restore the original window size.

This "lag" doesn't happen every time I start Minecraft, so sometimes it's enough to just restart it a couple times, maximise, and see if the title screen is animating smoothly.

The fact that Minecraft reports 35-45 FPS, I've got the latest ATI drivers (and saw this issue on earlier versions as well), and that I've had some complete hangs when maximising a lagging Minecraft window (only AltGr–SysRq–REISUB worked, not even Ctrl–Alt–F1), leads me to believe that the window manager, X or graphics driver is to blame.

Anyone having the same issue or tried-and-tested fixes?

Hardware:

• ATI Technologies Inc Cayman PRO [AMD Radeon 6900 Series] with BIOS from 2010-11-24
• 6 GB RAM
• Intel Corporation Xeon 5500/Core i7

Software:

• Minecraft 1.0 through Snapshot 12w08a
• Catalyst 11.12
• GNOME Shell 3.2.1
• Linux Mint 12 x86_64 with all the updates

On the same machine, when booted into Windows 7, I get over 100 FPS, and a completely smooth experience.