I finally solved the problem.
It's just that the HD enclosure (Nexstar NST-350U2 3.5" USB2.0) I was using was problematic. So I went out and bought a new HD enclosure (Nexstar NST-360HF 3.5" USB+Firewire). I used firewire instead of USB (dunno if that helped) and I partitioned my HD using GUID partition map, and since then TM was able to backup successfully.
Gee...Apple should have provided more technical info about TM. So many of us have wasted too much time figuring out how to make it work!
Btw, FYI, TM needs approximately 1.2x of your used space to begin an initial backup. See my other thread:
http://discussions.apple.com/thread.jspa?threadID=1240678&tstart=0
Good luck folks!