Upgraded to 2.5.1, permalink not working.

I just recently moved my domain plus my blog. With that, I had to upgrade wordpress to the newest version, 2.5.1. Everything is installed correctly, except the permalinks won’t work. After I change them to the pretty style with /%year%/%monthnum%/%day%/%postname%/ I get a 404 error. I tried reading about the .htaccess file, but I do not seem to understand it. Can someone help me on this problem?