Re-installing everything is a must, IMHO Tony deserves a second star for this absolute truth.
Use the original CDs rather than a full backup from last week because the hackers might have been present for a long time.
If possible, try to find how they entered because if you don't tap that hole, the history might repeat.
If you want to investigate, mount your filesystem in read-only mode (so you won't modify or overwrite any evidence) and eventually make a copy. After re-installing, you will be able to compare the original files with the copy and detect eventual modifications in the OS binaries and in other critical files.
If you don't have one, a system like TripWire would be very useful in the future.