The great thing about owning my own laptop is I can put the code onto it and bring it into work so I can play with it at lunchtime - fab! So, I've made the change where by I now no longer have a bitmask marking the rotations that have been cached, I now just use the cache index value directly and if its 0, then its not cached. This works great, and frees up 167 bytes (space for 4 more sprites!) Not that you really seed a speed up, but I know its a little quicker, so thats nice.
The next thing to do is to try and finally make the cache work the way its supposed to! This simply means keeping commonly used rotations in there, and letting ones I don't use much drift to the top of the free list - I hope to do that later tonight.