First possibility is that the immutable flag is on. You can change this behavior using the command
chattr -i filename to allow the changes to the file.
But maybe you are running a filesystem with errors; this can make your filesystem become read only entirely or for certain files. Troubles with the RAM can emulate this problem, too. This can be fixed when you reboot the server and runs fsck, but sometimes the server can fail to start and data can be lost when the reboot operation tries to synchronize the information in your RAM to the disk during the restart. If dmesg shows that you are running with memory or filesystem errors, I would recommend a data backup before the reboot, if that is possible. Sometime bad addresses of memory are given by the kernel due to hardware troubles, and some bad data can go to the disks when the system restarts. A crazy kernel is worse than a kernel in panic, and can do some unexpected behaviors like write in your MBR, or important files; it is rare but possible in bad hardware, particularly if you run with bad RAM or with a hot processor. In Brazil, we have a large amount of bad hardware that can cause that. Note: If the trouble is with the RAM memory, don't run FSCK -- it will do crazy things.
UPDATE: Because you're saying you are having troubles only with tmp there is a chance that tmp is being mounted in another partition (with errors perhaps?) or externally (samba, nfs?), so in this case we need more information about your mounted partitions. If that is the case, post the result of your
mount command without any arguments.