When you open the supplied blend (http://www.pasteall.org/blend/11481) you'll see that there is a grid. If you play back the animation, all parts are moving, but not rotating. If you let the animation cycle (let it play more than once without hitting alt+a again, the parts are rotated from frame 1!
Windows XP and Ubuntu Linux
2GB, Crappy Intel Card
Findings so far:
The problem is with reading point cache particle state. For non-dynamic rotation mode the rotation values are not actually stored in the point cache. Instead the rotation state is reconstructed after the other particle data is read (pointcache.c, line 320). And that doesn't produce the correct result ...
Idea discussed with Janne Karhu: use something like the basic_rotate function to reconstruct the rotation properly. As it turns out, this is not possible either, since for the default "spin" rotation mode the actual rotation quaternion still depends on incremental changes of the angular velocity, calculated from the change in velocity vectors. So that looks like a dead end.
Only feasible solution it seems is to bite the bullet and also store rotation values for "Velocity" rotation axis. Not sure if this is necessary for other rotation axes as well.
Fix committed in r44977. As Lukas found out it's pretty difficult to calculate the rotations implicitly, so the solution in the fix is to make particle rotations completely optional. The particle rotation panel now has a new enable-checkbox in it's header that toggles whether rotations are calculated at all. If they are, then they're also always stored to the point cache and the kind of incorrect rotations as described in this bug report shouldn't happen any more.