Hey orrarah,
This sounds like it could be a permalink issue. Try going to your Wordpress Settings>Permalinks and selecting default so that you aren't using any kind of pretty urls. Save and test the pagination again.
If it works, you can try setting your permalink structure back to just postname and the refresh might have solved it as it sometimes just needs to be refreshed like this. If it does not, you'll need to go through the wordpress troubleshooting steps for permalinks: http://codex.wordpress.org/Using_Permalinks#Fixing_Other_Issues
There is a glitch with the way wordpress generates the .htaccess file and there are steps just below that link to assist.
Regards,
Devin