Ehh well first rule: no tables for laying out your design. DIVs only!!
I've read and re-read your post but I'm having a hard time trying to figure out exactly what you're looking to do.
If you just want a header thats a graphic...yeah use PS and design it. You could always put navigation text links in it/below it as an unordered list. Mock it up in PS and see what looks best to you.
If I'm way off here just reply and try to be a little more specific. :-S