.htaccess URL Rewriting not working in production

Question

I am working an a small REST API with FlightPHP, and having an issue with the URL Rewriting. It is working fine on my development machine, but when I deploy it to production I am getting 404s for all routes other than the base '/' route. The 404 is not the typical FlightPHP 404, but the Apache/Ubuntu 404

This is what I have in the .htaccess:

RewriteEngine On
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)$ index.php [QSA,L]

I know .htaccess/mod_rewrite is enabled, because I also have a couple of WordPress sites hosted on this machine (a Linode VPS)

Any ideas?