If you still experience lag, try dropping down your resolution (assuming you are running at higher than 640x480). The main reason for lag is the fact that osu! is highly dependent on pixel shaders, and some older/lower performing cards don't have great support for this yet (although all newer cards, 2005+ish should do fine).
It might seem strange and look like its my fault that such a visually "simple" game can lag on some systems, but the truth of the matter is that drawing 2D in direct3d requires a relatively large fill-rate - in many cases more than a recent 3d game. This is due to the textures being huge, and always fully visible, with no/little optimisation from mipmap compression when resizing (because the sprites are usually drawn at full size).
The biggest draw on fill-rate is drawing semi-transparent sprites which overlap others. This is referred to as overdrawing, as each pixel which has more than one sprite must be drawn more than once. With several sprites (even when they are fully transparent at the area to be drawn) this can get relatively complex and graphically intensive. The best example (as has been mentioned already in this thread) is star bursts and fire effects.
In short, try dropping your resolution and upgrading your graphics card's drivers, and also disabling fire effects. I may add an option to also reduce other effects such as star bursts in the near future if peoplea re still having issues with them.