Brad,
My interior is almost entirely teak -- one of the benefits and curses of a Taiwanese boat. Unless you're got plenty of portlights or a really good interior
lighting set-up I think you'd be well served to go with white in the storage areas. The reflected light makes a huge difference when you're digging around trying to find stuff.
Clean, scuff (sand, wire brush, or scouring pad -- double check your
paint instructions for what they recommend), clean, prep-wipe (again, check your
paint instructions), and
paint,
paint again (and again) if necessary (check paint instructions for recoat times).
I've had good results with Rustoleum enamel for interior cosmetic stuff like this in normally dry areas. For areas below the cabin sole, I'd recommend BilgeKote -- it's a really tough paint that is very forgiving during application.