I've never used the free unlock tools so I can't comment on how good or bad they work. I have used the one from
http://www.imei-check.co.uk/ It may cost you a little $$ but it works and there are no headaches.
I have a 5600 from AT&T that I have been using on my carrier (Fido) since I got the phone back in November of 2004.