What about the robots settings -- index,follow? Is that set correctly at your site? Do you allow spiders to crawl your site?
To AndyRay: well, if the pages cannot be found, you should check closer for reasons? Did you try Google's webmaster tools to see what is the indexing status for that site? Are you feeding Google your site map? If yes, is it correct?
There may be plenty of reasons for that... maybe you could try to check out at some SEO related pages as well; these are moreless ment just for JoomSEF problem and I am not really sure, your problems are related to JoomSEF.
Anyway, if any visitors knows, he is free and welcome to help your here of course. :)