Time Machine gives Backup Error after changing backup drives

I recently changed by backup drive from an external 500GB HP drive to a 1TB Toshiba drive and Time Machine now gives me an error message. I should note that Time Machine worked perfectly on the HP drive, never had a problem with it.

But with the Toshiba drive I continually get an error message saying "Unable to complete the backup. An error occured while creating the backup folder." This message, along with the fact that I am unable to copy or create (i.e. new folder) anything to the drive made me at first think it was a permissions issue. I did both a Repair Disk and Repair Disk Permissions. After those the backup will run successfully about 4-5 times and then start giving me the same error message.

I happened to take a look at the Console and it throws me this error message: "Error: (22) setxattr for key:com.apple.backupd.HostUUID path:/Volumes/Time Machine Backup/Backups.backupdb/[My Computer's Name] size:37"

(Also if it's of any consequence I've also tried reformatting and renaming the drive several times, but it's the same thing like when I do Repair Disk/Permissions. Works fine for a few backups, then gives me error message.)

Anybody have any suggestions? This is becoming quite frustating and irritating.

Thank you in advance for any and all advice.