@jaimed I ended up having to create a category.php and a tag.php file. In all my previous themes, it automatically picked up the archive.php file for these but I guess it’s not doing that any longer. I did that, then I went into the permalinks, changed to default and saved, quit out of WP for good measure, then went back in and changed the permalinks back to my custom preference. Seemed to to it. Hope it helps you.
I found this reply from one of the moderators on another post and it helped with my custom post pages, but I’m still trying to figure out the issue with category widget as it pulls up the same 404 error. I might have to hard code that instead of using the default widget I suppose
http://wordpress.org/support/topic/pagination-for-custom-post-types?replies=40#post-1620769
I don’t use that plugin and the issue still happens when all my plugins are deactivated, but thanks for your reply.