You can change the basic colors, the logo, the new thread/post reply buttons, all of the icons next to threads, and basically any GIF item you see. Many items such as category headers can be replaced with images such as is done in the One Ring to Rule Them All theme. Background images can also be done as seen in the Tenchi Muyo! and Midnight Seduction themes. You can also change the colors for Who's Online.

As for the things whose colors can be changed with hex codes, those would be background, text, page background color, user info color, table border color, category strip background color and text, table heading background color and text, 1st and 2nd alternating background colors, link color, hover color for links, and time color.