Numeric pagination not working (404)

I’m using a numeric pagination and having an issue with it I can’t figure out.

I’m using the custom permalink structure /%category%/%postname%/ with my .htaccess setup (everything works other then pagination). But when i try to go to /news/page/2/ it redirects me to a 404 page (well home page since I don’t have a 404 setup yet). Using /category/news/page/2/ works fine. Same with using /news/?pages=2 not working but /category/news/?pages=2 works.

I can get to/news/ or say or/news/post-name-here but /news/page/2/ is not found, as with any other category.

Any suggestions? this is really frustrating me, and having /cateogry/news is not an option due to the required structure of the projects urls, needing /news, /blog /othercategory and so on.

Thanks for the help!