Pagination not working on products page

I'm almost done customising everything, only to find out pagination is not working on products page. When I try to change pages by clicking on the page number at the bottom, all the products disappear from the list as well as the bottom pagination links. The same happens when I try to change the number of products displayed or the sort order. I noticed that after any of those changes, a "#" is added to the end (or the middle) of the URL string.
The funny thing is that, if I copy the new URL with the # and call it directly from the address bar at the browser, it works fine.

Any possible solution? I can't go live unless I solve this annoying problem!!!

Thanks!

P.S.: The site is not live yet. It's running on my localhost so I cannot give access to it. Could upload to a temporary host if absolutely necessary