That may be the case that you stated. Have you made a sitemap and submitted it to Google. This action can sometimes clear up any some issues that your site may have with being properly indexed.
Yes I do have a sitemap submitted for this site, however it doesnt have all the links just the top level. Im creating a new sitemap to include all the links so hopefully that should resolve the issue.
On page links help Google determine the importance of pages. I would recommend having on-page links to all pages you want indexed by Google (in addition to separate sitemap links). I would also avoid having more than 100 links per page -- it looks spammy.
Too many links per page is just one of many variables Google looks at but, for already low-ranking pages, it may take on more importance.
I think Google would find all your links lastly and you would not be punished by Google for so-called too many links on pages if only they were not just there for increasing link popularity purpose.
Of course, a well-done XML sitemap would be helpful for this purpose and it also help in deep indexing.
Although there is no clear evidence to suggest that having 100 links per page will lead to direct penalization, I would still avoid such practices. Put aside SEO point of view, having 100 click able links does make the whole page looks odd.