After a fair bit of tearing my hair out and frantic searching I finally managed to sort out my indexing problem, and the custom search used by google adsense for search works now. It turns out that the problem was that I was using relative paths in my linking, and somehow this meant that the page was calling some of the link recursively, causing the robot to die, even with a sitemap.xml still submitted. I changed my php so all my paths are now absolute and bingo, problem solved. I have no illusions as to this suddenly shooting me up the search ranking but as least it can not search within my site, making it looks that tiny bit less rank amateur.
The way I found the problems was first I looked at my page using a Lynx viewer. Lynx is a text based browser and I'm told that what it sees it very close to what the robots see. It saw lots of links that didn't work. I tried creating a sitemap at http://www.xml-sitemaps.com/, which is an awesome site. It generated a huge sitemap which had all 500 allowed links for the free version. I checked the forums there and saw references to the problem, changed my links and booyakasha, I now have a site that indexes. I used the sitemap generated there (I was so happy I even uncharacteristically made a donation) and now all my pages are showing up. Went back to lynx and now I can move around my site with Lynx, googlebots are happy and I can move on to my other problems.