I have all of those apps installed as well so I doubt it's a conflict. Otherwise I can only offer the same advice as orbital; try it a couple of times and maybe it'll eventually work. Yes, there's no good reason for this, yes, we can't explain it, but if it works, it works. (and it has for others with other apps)

Bizarre. My luck by the way, was having it install on the first shot for both the firmware it came with, and the subsequent week 51 update I flashed it with. XTerm's pretty much a requirement if you want to do anything fancy at this stage... If your DejaPIM isn't too full of info I'd clear all apps and try again. At that point if it still doesn't work, reflash and give it a go.

If that *still* doesn't work for some crazy reason, you might want to try having someone send you the .desktop file associated with XTerm and manually copying it into the /etc/others-menu/<whatever>Extras directory. You can edit that directory without root access.