Have they checked website optimizer? Google isn't a call me and let's talk about it company. It has very efficient and streamlined tools to help people figure out what is wrong.
There's a good chance there is an indexing problem that could easily be rectified if they just check webmaster tools.
(PS. Ditto on the misleading URL)