I had all the correct code in the .htaccess file, but it ended up being completely overridden in the Ubuntu default /etc/apache2/apache2.conf file as well. Changed the entry for / and /var/www from AllowOverride None to AllowOverride All, restarted Apache and now everything works just fine.
