I got my sprite manager cleaned up, and the rest of the code too. Scene objects now add themselfs to the scene graph when they're set to visible. That way the application doesn't have to do it. It also means that sprites can add themselfs to the sprite manager instead of the scene graph. This might come back to bite me when I do culling though.
I also store pointers to sprites in my multimap in the manager, instead of by value. That got me 5 FPS (From 62 FPS) where I was adding/removing 12 sprites per frame, which is a fair bit.
Compile is nearly done, back to work...