Actually it's the theme that supports the header option, not wordpress. Most themes, even the ones hosted here do not support this option and have been worked on by the system admin. It's a simple CSS change actually. Heck, you can even switch files if you want. just keep the same file name.
- Complain to bluehost about their lack of support. While you're doing that, complain about their support of spammers and inability to follow up on abuse complaints too ;)
- Find yourself a real host. (My two cents -> synhosting.com)
edit: all the themes with header support on my own wpmu install, I've done myself.
reedit: What version of wp do they offer over there anyway?
rereedit: Probably should be over at wp.org for this but since you've already asked and I gather its a transfer, we'll take it.