Yeah I don't think Validator will pick up on the mulitiple use of h tags. Google "<h1> tags" or something like that. Like "how to use <h> tags". Also you may want to change the text that is in your h tags. Meaning in your <h1> tags you have, "Menu 1". This will only help you if people google "menu 1", so unless you want to be ranked high for the term "Menu 1" I might want to rethink that.
I am in the process of finally validating my site and putting in my <h> tags so have been reading some stuff on them. I kinda ingnored the structure for the longest time.
Now while validating is nice, it is not necessary to have a good site. I want to validate I think cause I have never been able to do it. If you validate some of the most popluar sites like a Ebaumsworld, Collegehumor or whatever most will never validate, at least when I was checking like a year ago.
In you <h> tags is what you want people to search for or should be titles to content.
IE.
Fruitsandvegetables.com
<h1>Fruits & Vegetables</h1>
Blah blah blah content
<h2>Fruits</h2>
mmm I love fruits blah blah
<h3>Watermelon</h3>
Oh these are the best blah blah
<h2>Vegetables</h2>
etc....
You will have much better search engine optimization going on...