Time Machine problem with iMac and TimeCapsule

I have an iMac (27inch, late 2012 model running 10.9.3, 32GB 1600MHz memory, GTX 680MX 2GB, 768GB SSD) connected to a 3TB Apple Timecapsule via the wired network.
It was doing the time machine backup for a long time until it started to give me errors about 3 months ago.

I deleted the sparsebundle and tried to start from scratch, still no go.

iMac has all updates and patches and so does the Timecapsule through the airport utility.

The error I get is "Time Machine couldn't complete the backup to "AirPort Time Capsule"". I look at the Timecapsule/data directory and there is an iMac.tmp.sparsebundle file with 12.5MB size. Deleting that file (and deleting it from the trashcan), the same thing happens.
Rebooting everything, same thing happens.

The Timecapsule does have the sparsebundles of the Macbook Air, Macbook Pro and 2 hackintoshes but not of the iMac 27". There are still 1.14 GB available on the Timecapsule and the backup is scheduled to be only 390GB.

I am stumped.