Rackspace Cloud and Permalinks

We’re trying to migrate our wp website to Rackspace Cloud, but our permalinks will not work. They are just throwing a server error: 404 page.

We’ve been chatting to a Rackspace support engineer for about 3 hours and he can’t help and instead just points us to the documentation which really doesn’t help.

Anyone else run into this problem and can tell us how Rackspace resolved this so we can get our engineer to fix it! I saw there was a previous post that was resolved, but it was clear on the course of action that was taken to resolve the issue.

Many Thanks
Graham