Just jumping in again, I've had 4 different Mac's (3 macbook pro's and an iMac) in my house at various times and they all were backing up fine over WiFi / Time Capsule. For the first backup, I connected with a 1GB/S ethernet cable, otherwise only via WiFi.
One thing I forgot to mention was that all of them have also been religiously running "Maintenance" scripts:
============================================
http://mactoids.com/automator-action-maintenance-38/
http://download.cnet.com/Maintenance/3000-18512_4-99454.html
Maintenance 3.8 for Mac OS X includes Repair Permissions, Verify Preference Files, Periodic Cleanup, Update Prebindings, Clear Cache Files, Update Locate Database, Update Whatis Database, Update LaunchServices Database, Rebuild Spotlight Index and Force Empty Trash.
============================================
I'm not sure if these Maintenance actions actually fixed or helped any of my Time Machine issues, but I figured I'd share the info for others to try...