The second time I installed it, it looked a whole lit different than the first. All my start menu shortcuts were there, unlike the first time, including mstsc.exe/remote desktop and it just worked.
Thanks again for the little nudge in the right direction.
You will receive my hefty bill.