I had the same thing - trying to do a first Time Machine back up of a new late 2012 27" imac with OSX Mountain Lion 10.8.2 onto 2TB time capsule (both straight out of the box) over wi-fi. I tried again after connecting directly with a LAN cable and got same message but with error 17.
read http://pondini.org/TM/C9.html, i edited the computer name by taking an apostraphe out but left a space between words from the sharing panel, then edited the base station name in the airport utility panel by simply removing spaces between the words of the name. Both computer and base station were already less than 25 characters.
Then went back into Time Machine where the old name base station name was still selected as "the disk" and the new no spaces name was available below it. removed the old one, reselected the new one and it seems to be working.
It took about 1-1.5 hours to 'prepare' the backup, then placed a "Time Machine Backups" icon on the desktop and proceeded to backup the 12.5GB on there out of the box which has taken about another hour with 3hrs to go so it says. The warnings say the first one takes a while but really? for 12.5Gb?
I'm having the same problem as kevin p. I followed the suggestion from http://pondini.org/TM/C9.html
and a few other places from Google search. But the problem persist. My system is running Mountian Lion an upgrade from Lion. The Time Capsule was purchased last week.
Can anyone help?
Could try this also;
"As a note from auto backup trials it also seems vitally important that the "Time Machine Backups" volume is not mounted and showing as an icon on the deskptop for the backups to successfully work. Seems to work if the Time Capsule "Data" volume is mounted but not "TM Backups"
I'm a complete apple novice so apologies if this sounds novicey, in fact this is my first and it came with OSX Mountain lion already installed (imac 27") but it made a difference for me as to whether it was the drive/folder was mounted or not i.e. when I double click on a drive like the timecapsule backups or data it opens it in finder and also mounts the drive (an icon shows up on the desktop). even if i close finder it still remains mounted - I have to rightclick on the icon and 'eject' it before the process would work for me, not just close down finder.
Otherwise, as i've found trawling through these forums to solve my issues, that what works for some doesn't work for others but there's always many queries addressed slightly different so keep searching - so far touch-wood i've managed to solve all my issues either in here or other discussion forums by googling my question.