Did you try to quarantine the trojan first? To quarantine, an antivirus will make the malicious code read-only, and since it will never run again, it's fixed. If you can find the trojan but can't remove it, that is your best option. You won't have to do anything else if that works.
If for some reason that isn't helping, then you'll have to format and reinstall. (At least, I prefer this to complex cleaning instructions with several pieces of software -- advice prevalent on the internet.) If you make a backup now, you might copy over the trojan, so I can't recommend it. You should work with an older backup. After your system is restored you can start making regular backups again, though.