According to Roy Palmer's book, the word Navvy first appeared in print in 1822 and it certainly is an abbreviation of Navigator, a labourer on the canal building, the canal building period overlapped the railway building so the same workers would have moved between the two. The song The New Navigation was written in 1789 for the opening of the Birmingham Canal, the start of a canal network bigger than Venice.
Comments about the interchange of nigger and navvy brought back to mind comments from one of our track inspectors (I used to work for British Rail) when he was offered a couple of West Indians for his gangs. He was widely reported as retorting "Don't give me niggers, they're useless, get me some Irish lads, they work like blacks" without realising the irony.
Amazing the thread is nearly 9 years old and still going strong