uvino? It sounds like you could use vnc to do the same thing, and it would most likely be cheaper. Sure the users might have to open a couple ports on their side, but since they're running Linux, they probably know to do that anyway.

EDIT: PS while you're with them you should tell them that it's not smart to allow people you don't know root access. Sure you (as a stranger) may be trying to help them now, but what about when you're off the clock, or alone? A separate account and some sudo privs might do all you need it to do.