WMT showing URLs not followed

My Sitemap Generator 2.5 has been working fine on vB 3.8 with latest vBSEO 3.5.

This morning I have a yellow caution sign in Web Master tools with the following text:

URLs not followed
When we tested a sample of URLs from your Sitemap, we found that some URLs redirect to other locations. We recommend that your Sitemap contain URLs that point to the final destination (the redirect target) instead of redirecting to another URL.

I opened up one of my sitemaps and found that each rewritten URL contains an /a/ in the url? Is this normal?

I deleted all of the .gz sitemap files in /data and rebuilt the sitemaps but when I open them I still see that /a/ I've not changed anything on my forum or my vBSEO settings in a few weeks.

Not sure, but this seems to be an issue with running 2.5 and vBSEO 3.5. I would try and downgrade vBSEO to the current stable 3.3.2.

so the /a/ should not be in the sitemap then.

3.5 was the first instance of vBSEO I've run. Do I just uninstall and then import my settings into 3.3.2?
Are there settings in 3.5 are not in 3.3.2? I guess I'm wondering if my RRs and Virtual HTML will still work.

I would definitely make a backup before you do anything and yes, try those steps.

Your RRs and Virtual HTML should still work as those both are in vBSEO 3.3.2.