Q:

root + crontab : permission denied

I'm using Debian 6, all patched up, but when I try to access crontab as root, I just get a permission denied:
root@server:~# crontab -e
-bash: /usr/bin/crontab: Permission denied

Please note this isn't as a user, but as root.
I haven't even got the foggiest clue how to resolve this if root has no access to the crontab.
Any ideas?

edit: answers are correct in 
a) yes there has been mischief (at least this is my suspicion) 
b) that my permissions on the crontab were screwy:
root@server:~# ls -lha /usr/bin/crontab
---------- 1 root crontab 30K Dec 19  2010 /usr/bin/crontab

so trying the chmod answer:
root@server:~# chmod 2755 /usr/bin/crontab
chmod: changing permissions of '/usr/bin/crontab': Operation not permitted`

and the package reinstall:
root@server:~# apt-get install --reinstall cron
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not upgraded.
Need to get 93.2 kB of archives.
After this operation, 0 B of additional disk space will be used.
Get:1 http://ftp.debian.org/debian/ squeeze/main cron i386 3.0pl1-116 [93.2 kB]
Fetched 93.2 kB in 0s (164 kB/s)
(Reading database ... 86601 files and directories currently installed.)
Preparing to replace cron 3.0pl1-116 (using .../cron_3.0pl1-116_i386.deb) ...
Stopping periodic command scheduler: cron.
Unpacking replacement cron ...
dpkg: error processing /var/cache/apt/archives/cron_3.0pl1-116_i386.deb (--unpack):
 unable to make backup link of `./usr/bin/crontab' before installing new version: Operation not permitted configured to not write apport reports
 chown: changing ownership of `root': Operation not permitted
 chmod: changing permissions of `root': Operation not permitted
Starting periodic command scheduler: cron.
Processing triggers for man-db ...
Errors were encountered while processing:
 /var/cache/apt/archives/cron_3.0pl1-116_i386.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

Is this going to take a complete reinstall of the system now to get this back up and running?
edit:
This is not a duplicate question - I had suspicions of a compromised server, but I'm not going to flatten a live server and rebuild it without evidence.
My original question was about the permission denied as a root user, as I was sure that was an impossibility, and I can assure you that I did search for that question first.
Thanks to the helpful folks here, I now understand the permissions more, and if this happens to someone else, they too will also be able to narrow down what has happened.

A:

OK, you already have part of an answer, having found the permissions on /usr/bin/crontab.
Now chmod is saying it can't modify those permissions.  Try lsattr /usr/bin/crontab to check if the file attributes have been messed with, and chattr -i /usr/bin/crontab to fix it if that is indeed the issue.
If this is foul play, then my guess is someone is trying to prevent you from finding and fixing something in the crontab data files.  Those are usually in /var/spool/cron/crontabs/ .  I wouldn't be surprised if there were more permissions or file attributes blocking your path, but you want to get in and audit those files smartish.  You might also want to look for other files that have their file attributes set oddly (in particular the immutable bit).
I'm sure it will be possible to get the system up and running again, but it's hard to say how much will be involved to do that, depending how much mischief has been made.  It's also likely that you would never know if you've really undone all the mischief.  A complete reinstall, or reinstatement of a backup is probably a good idea.
I note that on an up to date (such as that is these days, using LTS) debian 6 system I have handy, my /usr/bin/crontab is 35k, not 30k in size.  So consider the content of that file suspect, and don't run it.  Take a copy, then replace it from the distribution version.

