Permalinks Broken After Changing Servers

I moved my files and databases from one server to another on the same domain. The only thing that had to change was the name of the database and the username for the database. I made the updates in the config.php file and it loaded up fine. But if I attempted to navigate anywhere on the installation I would get File Not Found messages.

If I change the permalinks structure anything else, it will work. But if I switch it back to the custom structure I’ve been using forever, It doesn’t work and I get file not found. Here’s the permalink structure.

/%year%/%monthnum%/%day%/%postname%/

I need to retain the same structure since all the links to the posts and sites reflect that structure. I tried to upgrade the installation to see if that was the problem since it’s a version old, but I got this message when using the built in upgrade feature:

Fatal error: Allowed memory size of 33554432 bytes exhausted (tried to allocate 1316573 bytes) in […]/wp-includes/http.php on line 1358

Can anyone tell me what is going on here?