Note that on Unix (which I suppose applies, because you tried chmod 777) a file doesn't have to be writable to be deletable.  The directory the file is in, however, must be writable.  This is because the directory index needs to be modified to remove the file name (=link).

$ touch foo
$ chmod 400 foo
$ ls -l foo
-r-------- 1 er er 0 2011-03-15 03:05 foo
$ unlink foo
$ ls -l foo
ls: cannot access foo: No such file or directory
[download]

So, as for your problem, is the directory writable?