Are you using the WooCommerce stylesheets still? If not, activate them through the settings panel. If you are not using them on purpose, please make sure you take of the proper styling for the pagination.
You say it doesn’t matter which theme you are using, but have you also tried a default WordPress theme like Twenty Twelve? Does the issue still appear there? And can you please update your theme to the latest available version?