Unfortunately there are plenty of themes out there which aren't well coded. To be fair, WP themes aren't usually too bad but I've still seen a nice designed theme, installed it and discovered how much it breaks or fails on validation. You'll find a lot are coded to XHTML transitional which isn't the best doctype to be coding to. It's not hard to get it up to strict standards, but you just need to bear in mind, a lot of these theme developers are actually just designers who aren't full time front end developers, they just know how to put web pages together, doesn't mean the code is good!
If the theme is nice and the validation fixes aren't too bad, I would just fix them up (post up here if there are some you're not sure of!). I recently grabbed a quite popular theme off there (I'm sure it wasn't when I got it!) and my whole pages menu disappeared, couldn't for the life of me work out where it was besides off screen somewhere, but with a bit of food bribery Mr A came to the rescue and got it showing again

On a side note, the custom menu that Mr A mentioned would be very useful for your top horizontal menu, as you can have complete control of that then, mix and match links to pages, post categories, individual posts (if you wish), external links etc. Your horizontal menu at present is probably wp_list_pages() for the top level pages only (depth of 1) which means you're needing this extra plugin to hide specific pages, whereas with the custom menu you would simply control which pages displayed.
You could still use the sub page code to display the sub pages in the sidebar as per Matt's code and the link I emailed, although I recently had to get some code that would cover all ancestor pages (child, grandchild etc) which I found at
http://cssglobe.com/post/5812/wordpress-find-pages-top-level-parent-id.
Also, a second sidenote, if you've used a theme from WordPress, be aware that unless any changes you make to the actual theme are done in a child theme (a second theme directory that's told that it's the child theme of the original parent theme), then if/when the theme developer decides to upgrade their theme at all you will get notified of an upgrade for it. You don't have to upgrade so just be aware of this because if you do, all of your changes instantly lost! Hence the reason for the child theme approach to be better (although whilst I know this, I rarely follow my own advice!)