If all else fails, try installing a different application that requires python, like Canola or PyPackager. Since these are in the repositories, they will automatically take care of dependencies. Although, if pyRdesktop installed without any errors, that shouldn't be a problem...