The 'move-data > reinstall everything' routine was a common exercise for windows installations. For any Linux distro, only a fresh installation is enough (assuming the existing one has really been infected, and we are unable to clean it). This is because even if a file is infected (or a virus itself), linux doesn't execute it automatically (unlike windows) just by accessing it. It can get executed only after seeking explicit permission from you. However, presuming the threat was real, the existing installation may have it included in some auto-start routine, that's why a fresh installation is suggested.
Although there are really good tools in linux for virus and rootkit detection, (of which 'clamav' is in default ubuntu repo, rkhunter is already included in Backtrack live DVD), since we are suspicious of a custom script in your case, which these tools may fail to detect with normal options, a fresh installation is the best way to go.
Now if the attacker is not a professional hacker or security expert, the chances of him being able to infect your whole system is next to zero. Assuming that true, just a re-installation of the Linux part (after formatting the partition) is enough. Then change your passwords from the fresh installation. No need to change any passwords if you have already done that from a DIFFERENT computer.
But yes, IFF the data files are also infected (A BIG funny Question Mark here ), they may get carried. That's why I said "your trusted data" in my previous post. However, as I stated in the first paragraph above, they can only pose threat in windows environment.
That also brings up an interesting thing to consider - a code, which can infect files, thus allowing unauthorized access to the system, can either be designed to take advantage of linux, or can be designed for windows. Since the attack (??) was made in linux, it means the code should be harmless for windows unless it is some platform-independent script lying around as a file, waiting to be executed manually (like the php script you were handed).
So the summary is :
Just delete and quarantine any suspicious files (from your description so far, I can suspect none excet that php script), reinstall the linux part, allow it to overwrite MBR (it will, by default), change passwords as required, and you should be all good.
As for OS recommendation, while Backtrack is a really strong and one of the most secure OSes, it is not meant for normal day-to-day work (although you can do so by just installing additional software). So I'd suggest Ubuntu 12.04 64bit or 32 bit if your system does not support 64bit. If the system has less than 1GB RAM, install Lubuntu or Xubuntu instead.
And as for me checking your system (as per your pm), I simply can't for two reasons -
- I'm not an expert as you have mistaken me for,
- I'm on a crappy gprs connection which typically takes 20-30 seconds to just open a page, so using any remote service to offer help like that is beyond my dreams at the moment.
Oh and there's a third reason as well - You've just suffered one threat, don't risk more !
Good luck !