You don't need to build a relay shutter mechanism yourself, there is one available here http://www.techno-stuff.com/relay.htm
All you have to do is open the wired remote from ebay, note which wires are the common, focus and shutter, then connect these into the relay module. This has been done here http://www.flickr.com/photos/73571158@N ... 3635436569
using a radio controlled remote but the principle is the same.
I can understand that you might not want to risk damaging your camera but there are probably either infra-red or radio-controlled remotes available. Since these have no direct connection between the relay and the camera the worst that can happen is that it simply does not work.
At the moment you are having to program the NXT to work in conjunction with the intervalometer, over which it has no control. If the NXT is operating the shutter then it has full control over both timing and movement, and not limited to the timing restrictions of the intervalometer. If the two units are acting independently, in a long time lapse you are likely to miss shots because the shutter fires when the robot is moving.
Does the intervalometer make a sound when it operates? If so, you could possibly use the NXT sound sensor to detect when the shutter has operated and use that to coordinate the shutter with the movement.
Whichever way you do it I like the idea of using movement to give a 3D effect on the timelapse and shall be following your progress with interest. I wonder, if you built a curved track would that save you from having to make the pano head rotate?