I think the jury is still out on AJAX and Accessibility, the current rule of thumb is that you should have a non AJAX alternative.

Most Accessibility guidelines suggest your site should work without Javascript enabled. This is because many screen readers cannot react to Javascript invoked changes, (sounds like this is the issue your clients are having) it has nothing to do with whether a users browser has the Javascript option enabled. I dont think there's any 'cure' for this I'm afraid.

Some links:
Bruce Lawson’s personal site : accessibility web standards
accessible.ie

Des