If you've got a different hosting provider, try using that instead, as the issue might be down to your hosting provider.
Anyway, it's strange. I'm also curious to know what caused the issue. If you've said that mod rewrite is enabled and there's no problem with the .htaccess file, then the redirection should be working fine. Maybe the developers can help you out.