Did you get the replacement from Apple?
If not, check the wattage on your replacement power supply. The powerbooks had a higher wattage requirement (67 Watts?) than the iBooks (45 Watts?) even though they had the same connector.
I purchased a replacement adapter from eBay and it ended up being the 45 Watt version for an iBook, and it gets VERY hot when charging my Powerbook G4.
This was hot on the physical adapter though - not on the end of the wire...
Also make sure the plug has a good connection where it plugs into your powerbook. Maybe it is loose?
The fact that the fans run all the time seems like an issue. It may be getting hot just form the heat in the powerbook. You might want to talk to apple again, because your fans shouldn't be coming on all the time, unless you are pushing it hard with video, etc...