Is anyone having trouble with Time Machine after updating to Mavericks?

Getting this message after the first automatic backup: "Unable to complete backup. An error occurred while creating the backup folder". Backing up to a Seagate 4TB desk top hard drive. Worked fine in Mountain Lion. Tried a new User ID and also Safe Start with no improvement. Apple advises reloading the entire operating sysyem! Sound like the good old days of the PC have caught up to the intel-based MACs, unfortunately. This is very troubling. I have been a MAC user sunce the 1980s and still have all my old MACs, about 15 of them. Can somebody help me?