Does the tmp directory have to be shared between servers? I am having a problem with multi file uploads and I suspect the issue lies in the fact the tmp directory is not not shared between servers.

Does it have to be shared between servers? I have 2 webheads (server boxes) and both have a local tmp directory (not shared between them).
Yes, if you have multiple servers serving the same domain, then you need to ensure that the two Drupal server instances share the same filesystem. Best is to use NFS mount, so it is physically only one folder. You may get by with rsync in a cron depending on how the filesystem is used in your application.