i assume you're using mstsc.exe, right?
if youre using RDC, what error do you get (if any)? can you describe exactly what you do and exactly what occurs that leads you to the conclusion that you can't establish a connection without first having logged on locally?