Only numeric publishing of posts work

I just migrated my blog to another server, I even updated to WP 2.5., really nice except the fact that my permalinks with customestructure /%postname%/ does not work anymore. It gives me a blank page with an error saying. The requested URL /XXXXXXXXXXXX/ was not found on this server.

Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.

I already deactivated my plugins, checked, activated and checked if it was working.. But it’s not giving me the posts.

What else can I do?