Try to reset Sprites and Bg after each game ?
Are you using Palib ? :
You then need to reload all sprites.
It may be good also to clean your BG and reload them.
At least, that's what I do when the main menu load, the Game load, and when anything Reload.
In fact, I have a Reinit function which is called right after loading palletes and Initiating things. It is recalled anytime by writing with "reinit()". It works pretty good that way, even if I have a 8142x4096 pixels Bg ; )