Time machine cannot access the sparsebundle (error 112)

I am having a problem with my time machine backup, i.e. no backup occurs.

MY NAS details are:

Model: ReadyNAS NV+ [X-RAID]
Firmware: RAIDiator 4.1.10-T3 [1.00a043]
Memory: 256 MB [2.5-3-3-7]
IPv4 address:: 192.168.1.101

When I use Time Machine on my Macbook Pro (running OS X 10.8.1) I am able to select my NAS as a backup disk. It requests my username and password which I provide and it seems to connect successfully. However, it can never 'locate' the backup location.

Time Machine will sit there for a couple of minutes saying "Looking for backup disk..." and will then give the error "The backup disk image "/Volumes/ReadyNAS/Petra.sparsebundle" could not be accessed (error 112)."

An example from my log:

19/09/12 2:16:11.204 AM com.apple.backupd[4341]: Attempting to mount network destination URL: afp://ReadyNAS@pandora.local/ReadyNAS
19/09/12 2:16:16.000 AM kernel[0]: ASP_TCP CheckReqQueueSize: increasing req queue from 32 to 128 entries. so 0xffffff802a267ba0
19/09/12 2:16:17.503 AM com.apple.backupd[4341]: Mounted network destination at mount point: /Volumes/ReadyNAS using URL: afp://ReadyNAS@pandora.local/ReadyNAS
19/09/12 2:16:17.000 AM kernel[0]: ASP_TCP asp_tcp_usr_control: invalid kernelUseCount 0
19/09/12 2:16:17.000 AM kernel[0]: AFP_VFS afpfs_mount: /Volumes/ReadyNAS, pid 4428
19/09/12 2:16:17.000 AM kernel[0]: AFP_VFS afpfs_mount : succeeded on volume 0xffffff81a4ab6008 /Volumes/ReadyNAS (error = 0, retval = 0)
19/09/12 2:16:41.000 AM kernel[0]: hfs_mounthfsplus: BTOpenPath returned (5) getting catalog BT
19/09/12 2:16:41.000 AM kernel[0]: hfs_mounthfsplus: encountered errorr (5)
19/09/12 2:16:41.000 AM kernel[0]: hfs_mountfs: encountered failure 5
19/09/12 2:16:41.000 AM kernel[0]: hfs_mount: hfs_mountfs returned 5
19/09/12 2:16:42.637 AM com.apple.backupd[4341]: Failed to mount disk image: Error Domain=com.apple.backupd.ErrorDomain Code=21 "The operation couldn’t be completed. (com.apple.backupd.ErrorDomain error 21.)" UserInfo=0xXXXXXXXXXXXX {MessageParameters=(
"/Volumes/ReadyNAS/Petra.sparsebundle",
112
)}
19/09/12 2:16:42.879 AM com.apple.backupd[4341]: Ejected Time Machine network volume.

The backup used to work, and then all of a sudden stopped working. It may have been around the time I installed Mountain Lion.

Any help would be greatly appreciated! I have looked everywhere but can't seem to find a solution. This has been going on for almost a month now!

Thanks!