I have the issue fixed now.
I was thinking the same thing about sh404SEF, which is installed. I had cleared all URLs that were related to the product in anyway before posting the support ticket. So after you mentioned sh404SEF I was much more aggressive in purging URLs, and aliases. After deleting anything related to the product category, then the entire category threw a 404 error. So I purged all URL's and aliases and let sh404SEF rebuild the URL's. That solved my new issue and the support ticket issue.
Thank you for pointing me in the correct direction.