vezy

For those of you who land on this – follow batikandgift’s suggestion above

Found the solution,

Under wp_options table search for option_name = wpsc_category_url_cache
delete its contents and hopefully your pagination & categories link will be back to normal.

For those of you who don’t have a clue what he is on about (you were a few on here i see), you access your MySQL, then extend you database by clicking on it, and click on wp-options table.(literally) Then find
wpsc_category_url_cache in the option_name list. Click on the pencil to edit and empty the information in the comment box.
This just fixed things for me.
Good luck!