404 header returned every time

I have a codeigniter app that works fine everywhere, but on 1 particular client's server the pages all load correctly BUT it returns a 404 header every single time.

This is preventing Google from indexing the site correctly.

Here is my .htaccess:

Code:

RewriteEngine on
RewriteCond $1 !(index\.php|images|robots\.txt)
RewriteRule ^(.*)$ /cidx/index.php/$1 [L]

also

$config['uri_protocol'] = 'AUTO';

I've tried multiple to no avail.

Any ideas?