Well, I logged in to my Google Apps mail tonight and Google finally decided to roll out "Themes" to my Gmail. I'm not sure why it took them so long, but at least it's hear. What's really weird is most of the other "Lab" tools seem to arrive pretty much in sync with everyone else—but they really waited to give me access to the Themes.
Anyway, I can finally change up my Gmail mailbox!