To get the URL rewriting working in WP I had to edit the apache config and change AllowOverride None to AllowOverride FileInfo. I then got the URLs working properly, but Apache didn’t seem to like it at all. I had lots of instances spawning constantly and bringing the server to a grinding halt (a load of 30 is quite a pain).

I noticed that I had a lot of error messages in Apache’s error.log:

WordPress database error MySQL server has gone away

I got it working in the end by applying this patch.

Edit:
The above was only a temporary fix. In the end I had to revert to the original setup without Rewrite URLs.