This is something that gave me a lot of trouble once upon the time (I'm working on a total interface change), but it's actually really easy. Under your Civ4 or Warlords folder go to Resource/Themes/Civ4/ and backup Civ4Theme_Common.thm. Then edit the original. You can open it in any text editor
Look for line 204 at the end of the line you should find "GColor( 69, 93,156,217)" The four numbers in the brackets are what you wanna change. The first three are Red, Green and Blue values, and the fourth is alpha, or transparency.
Just two things though: 1) You might find that there are other things you'll need to change to make everything look right with the orange, but the main things you'll wanna change are all in the following three lines, and 2) Don't go for BRIGHT orange: it will kill your retinas.
I hope this helps!