Transferring to New Web Hosting

I had a working wordpress blog on a free web host and today i finally bought a new web host for better reliability.

To transfer my blog onto the new Web Domain I performed the following in the given order :
1) Changed the Name servers
2) Downloaded the entire Blog from public_html from the old web server and uploaded it to the new one.
3) Backed up the entire MySQL database from the old web host and restored it into the new one.
4) Updated the wp-config.php file with the new database entries.

The home page is now loading, so is the wp-admin/ and dashboard.
But every other link on the home page is not working.

I am receiving the following error :

Not Found

The requested URL /resume/profile-summary/ was not found on this server.

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

How should I solve this ?