Laurence, it's a tough problem. See the following links:
http://en.wikipedia.org/wiki/Automatic_label_placement
http://www.szoraster.com/Cartography/PracticalExperience.htm
http://www.eecs.harvard.edu/~shieber/Projects/Carto/carto.html
http://i11www.iti.uni-karlsruhe.de/map-labeling/bibliography/
Gabor,
I've used convUL in the PBSmapping package to convert from UTM to
lat/lon for some weather data I was playing with. It will also convert
from lat/lon to UTM (I haven't tried that direction though).
Here's the code I used:
library(PBSmapping)
subs = read.csv("ngrid/SubAsPoints.csv",