Maxbox:
If BRU fails via right-clicking, the prob could be the right-clicked Dirs.
For example: how they're being served, permissions, etc..
If right-clicking G:\MySongs wont open BRU properly, then use:
"C:\Program Files\Bulk Rename Utility\Bulk Rename Utility.exe" "G:\MySongs"
Success proves a .dll problem in your case, failure suggests another culprit.
Others:
This 'feels' like Win8.1 accessing too much metadata (that BRU doesnt need).
Has anyone tried disabling Microsoft's new DLNA shell-extension (dlnashext.dll)?
The registry key:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Shell Extensions\Approved\{289AF617-1CC3-42A6-926C-E6A863F0E3BA}
You can set it to 0 and then reboot to prevent it from loading.
Sorry, I've no environment to troubleshoot myself (NAS/UPnP/Vista), all I can do is make suggestions.
If nothing else, its 1 possibility eliminated (just set it back to 1 if you must have it).
Good luck & keep posting, we'll get to the bottom of this eventually.