Time Machine giving error OSStatus 13

I have an Apple Mac Mini server running Mac OS X Lion Server and I got a new Time Capsule to do the backup.

I have set it up and everything's working fine except when i chose the Time Capsule as the back disk from Time Machine on the server, it gives me an error saying "Time Machine can't access the backup disk "Time Capsule". The operation couldn't be completed. (OSStatus error 13.)"

Then i tried it from my Macbook Pro and it works like a charm. So what am i doing wrong on the server? Can anyone please help me resolve this issue.

Thanks in advance.