Having trouble getting this up to your stated speeds...

Dolphin r4771 x64
Using DX9 graphics plugin, at 800x600 res, 4:3, other settings default
CPU: Q6600 @2.7GHz
GPU: RadeonHD 4670

Getting around 30fps in the actual level.  I notice that if I go into the graphics plugin config » Advanced tab and change EFB Copy to "To Texture", I get around 55fps, but the sprites look stuffed.
OpenGL plugin doesn't run much faster.
GPU doesn't appear to be the bottleneck.  With it downclocked as far as it can go, I get around 25fps in game.  Turning the clock up slightly, I get 30fps, and if I turn it up all the way, it's still around 30fps, so CPU must be the bottleneck I think.

You guys using any special settings or something?