I'm in the same boat and also worry about it to a certain extent. However, 7 years of getting paid to write software has mostly given me more confidence. Also, I know a lot of really smart people (a lot smarter than I) who studied Computer Science and couldn't program their way out of a paper bag.
I'm not 100% sure that fizz buzz is really the indicator that people make it out to be ... I mean, it doesn't really test software design skills, or the ability to design a complex system with loosely coupled objects.
Fizz buzz is very simple. It's easy to communicate, implement and test, there's nothing fiddly about it. It's the entry level indicator and requires no prior knowledge, other than the ability to turn a simple, stable specification into software.
If you can't do fizz buzz in your chosen language, then it's highly unlikely you can do anything more complicated.
It doesn't test your ability to do any kind of high-level design. It just tests whether you can program at all.
The ability to do high-level design is only important in one of these two situations:
1) The position you are hiring for only involves doing high-level design and not doing any programming.
or
2) The position does involve programming, and the person you are hiring is a competent enough programmer to do fizz buzz.
