Ended up being a group membership issue with the account used for the backup. The account had to be a member fo the groups Domain Admins,Administrators, Backup Operators,Enterprise Admins,Organization Management. Once I added it to the missing groups from that list, all worked fine.
Note that there is a bug that can lead to a very similar problem if you are using special characters in your account password., Thats what that hotfix you mentioned above corrects.
I hope this helps anyone in the future that has this issue.