There's no magic involved, just well-written code.

I ran the Free Rotate scene from the demo on a Nokia E50 (closest thing I have to a Nokia N70) and I think you will find the results I got very interesting.
Before I begin please keep in mind that, for each frame of the demo:
* the nine buffers (one for each image) must be cleared,
* the screen must be cleared,
* after the actual rotations take place and the results are stored in the buffers, said buffers must also be drawn on screen.
This is a significant overhead, especially when considering that images and buffers are stored internally as int arrays, for quick and dirty pixel manipulation, and that the results are drawn on a Graphics object - in this case the screen - using drawRGB.
Now, the results:
With the latest version of the library and the demo, the on-screen FPS counter shows 12 FPS. Since there are 9 items on screen, that's 108 rotations per second. With the overhead described above.
However, I also timed ONLY the rotation part of the code (with none of the overhead described above). I got 5 ms for each rotation, which means 200 rotations per second. Not only is this pretty fast, it's also closer to real-life performance, considering that in an actual game you will most likely draw the result on an Image object and reuse that object in subsequent frames (unlike the demo, which does not cache/reuse previous results at all).
In my opinion, this means that real-time in-game sprite rotation is more than feasible.

PS: The source sprite is 64x64. Smaller sprites will yield better results.