While having all those links in the main nav site-wide isn't necessarily helpful to SEO, I routinely deal with clients that have twice as many links in their drop-downs. So I agree with Marcus - it shouldn't be causing you serious problems.
In addition to Marcus' suggestion, I would recommend a couple things to work on:
1. Sub-navigation
Like you have in the Staff section http://www.ibethel.org/staff - by adding in sub-navigation (links within that section that appear on each page of that section, and only for those pages) you reinforce content relationships.
2. Referrer Code in URLs - Duplicate Content
You've got links that have their URL appended to track referrer source right on the site. On the home page - the graphic call-out box (large graphic with 3 smaller graphics to the right of it). These links point to internal pages but stick
"?referrer=front_page" on the end. And since your graphics rotate, that means every page linked from this area is generating its own duplicate content conflict. While some programmers say it's fine, it's not. You could mitigate this by pushing canonical tags across the entire site, however best practices dictate to eliminate this referrer tracking method completely - Google only uses canonical tags as a signal and not all search engines use it.
3. Site Speed
I ran a couple site speed tests - you've got some serious issues regarding crawl speed. Your home page images are huge files, and you take a second hit with lots of Javascript file loading times. - More than one check came in at over 13 seconds - that's not user speed - it's crawlability by search bots. I highly recommend looking further into that. If it takes search bots too long to crawl just one single page, some of the links on that page will not be found during any single crawl - and this alone could be part of your problem. Look to have those graphic images compressed without losing quality. Look to have your Javascript files compiled.
4. Store Issues
Your category pages (http://store.ibethel.org/Childrens-Resources/c236/index.html for example) have no paragraph based descriptions so you're missing out on an important way to properly optimize those category pages for SEO.
5. Content Organization
Also in the store - your Books section organization is a bit messed up. So your breadcrumbs are broken. For example on this sub-category page http://store.ibethel.org/Books-Books/c173_25/index.html the breadcrumb shows Store Home > Catalog > Books > Books when it should be Store Home > Books. Except when I go to the top level "Books" link in the breadcrumbs I get an empty page http://store.ibethel.org/Books/c173/index.html
6. Store Page Titles
In the store, when there's more than one page of products in a category, if I click down to the 2nd or 3rd page in that category, I get the same page Title. Every page title should be unique, so the simplest way to fix that is to append page titles with the page number. Like Music then Music | Page 2 then Music | Page 3 and so on.
7. Stronger Titles
Your page titles in the store could be much stronger - Having a page TItle of "Music" isn't going to allow your site to rank extremely well given how competitive that single word is. You'd be better off with titles like:
Christian Music | Online Christian Music Downloads
Or for "Childrens Resources" a better page Title might be:
Christian Parenting | Christian Education Reources
8. Store Home Page Duplicate
Both http://store.ibethel.org/index.html and http://store.ibethel.org/ work - so that's duplicate content - have the index.html version set up with a 301 redirect pointing to the http://store.ibethel.org version.