Thats really odd
Months of dealing with this issue, I finally post a question about it, and it fixes itself!
I don't know what happened, I wasn't working on this issue at all, but something I did fixed it. I was playing around with my /etc/hosts file to fix a seperate networking issue (which still isn't working) and suddently my xterms pop up right away. Huh
I think perhaps localhost was poorly defined or something and that might have screwed up xterm.
Well, thanks anyway