Ah, by 16*16 you meant the playfields, sorry mate (that should have been painfully obvious). It's actually a single playfield of 32 colours, with a 16 colour sprite background. I was using 16*16 but was still using sprites for the parallax background.
Everything in the players area is in a single 32 colour pallete, the sprites in the background are separate. I'm grateful for such small mercies
