OK RClayton
Do me a favour and post your permalinks structure.
I managed to duplicate the error and i believe that it's in Custom Structure of Permalinks.
Here's what i just DID:
Installed on a WAMP (Apache 2 and PHP 5.2) a new WordPress 2.5.1
No plugins, no themes, just what it comes with. I just used the latest XML Sitemap Generator v3.0.3.3 plugin to have the DEBUG feature.
I Started with default permalinks structure. I wrote posts, added categories, delete categories, new posts, link categories, assigned tags, remove some and everytime i did something I run the DEBUG. Everything was fine.
In my blog i also use TAGS4PAGES and thought that there maybe was a conflict so i installed this plugin too. I wrote pages, assigned tags, reassigned new or del older, messed all tags and categories but DEBUG was telling that everything looked OK.
Next thing was to make "pretty" permalinks. I changed it to DAY & NAME or NUMERIC still everything was just FINE.
Then i changed PERMALINKS to the structure I USE in my blog which is CUSTOM /%category%/%postname%/ and run the DEBUG feature and guess what!
Errors, Warnings, Notices
Notice: Undefined property: stdClass::$args in ../../wp-includes/taxonomy.php on line 1068
Anyone who has a custom permalink structure and use XML Sitemap Generator v3.0.3.3 plugin please DO run the DEBUGGER to see if it gets a similar notice.