Well it's not a perfect fix and this doesn't actually change the color scheme of the phone, but I found a way to *mostly* cover up the brown colors in a few key areas like: Text Messages, Contact List / Address Book, and Dial Pad.
I just downloaded these apps and played around with the color settings in the apps:
Text Messages - "GO SMS Pro", or "Handcent SMS" (I used this to change text message colors)
Contact List / Address Book - "GO Contacts" (I used this to change the colors of the contact list / address book)
Dial Pad - "GO Contacts" (I used this same app to change the colors of the dial pad)
Keyboard - There are a ton of keyboard apps in the android market of course. I turned on "Swype" for the defaul keyboard under the "Settings > Language & keyboard settings". It's got a bit of a learning curve but I like it so far, AND, the keyboard for it isn't brown! Bonus! 
