Just use an 8-bit background. (You probably mean without using a
background map, right?) It seems like it draws the backgrounds a certain colour when you first set a color in the palette. So use this code.
BGTop8Bit = Screen.Load8BitBG()
Screen.Initialize( 1, BGTop8Bit )
BGTop8Bit:SetPaletteColor( 0, 31, 31, 31 )
If you don't understand the code, check 8-bit background tutorial here:
http://www.bio-gaming.com/jeremy/dslua/index.php?act=tutorials