I know this topic is a little old, but for the record, I would NOT recommend using a Brillo pad to clean the 360 for a number at least two reasons:
1. Primarily, a Brillo pad will scratch the bottom of the heat sink. The bottom of a heat sink is polished to a fine tolerance, if there are any air spaces caused by scratches or any other microscopic defects, the thermal efficiency of the heat sink goes down. In a perfect world, your heat sink would make 100% contact with the die and thus have maximum heat transfer. However, this is generally not the case, but you don't need to make matters worse by going at it with steel wool.
2. If any small pieces of steel wool break off from the pad and either get stuck to the bottom of the heat sink or make their way into your 360's case, or worse, the motherboard, you open yourself up to the possibility of shorting a connection and possibly (probably?) frying your 360. This is not good.
Additionally, Brillo pads are impregnated with soap. I don't think soap will cause any harm directly to the system, but why would you want to test that theory.
As was suggested before, use a product specifically designed for removing thermal paste or use something that is less likely to scratch copper, like the edge of a credit card followed by a Q-Tip and rubbing alcohol.