Okay, so I figured it out. First I must say most of the problems I have encountered have been with the WordPress SEO plugin. I went to the SEO forum and found a temporary fix for the issue. But apparently it will work but if I edit the categories I will have to do this step again.
The fix was to un-check the category-base and save, then re-check it, and save again. Although not a permanent solution I am happy that I could figured it out. This is where I found the information i
So I am marking this a resolved and thanks again!