You can devote a portion of the palette exclusively to UI stuff, and then use the optional arguments of the tweak palette command to have every portion of the palette but the UI colors change.
variable (loop)
for(loop,0,-31,-1) do(
reset palette
tweak palette(loop*2,loop*2,loop*2,1st_nonUIcolor,last_nonUIcolor)
#might have to use this command multiple times depending on palette setup
update palette
wait(2)
# gradual fade out
For simplicity's sake, I may just use fuzzy boxes. I was going to do that, then thought it might be cooler to do a legit fade out. Another plan I had was to make the UI colors for the menu painfully bright, so they seem normal after the fade.