Since most of the message listings refer to Wainmans in Canada, I can throw some info in from a different point of view.
I am Kendell Wainman in South Africa. From what I understand, the origins of "Wainman" do indeed relate to the saxon "Wagon". As opposed to a wagon - smith (being a maker of wagons) being named Wainwright we are supposedly wagon traders or as Gordon speculated wagon robbers..
This is an interresting thing as apparently the Wainmans were notorious for robbing coaches and wagons in the Nottingham region of England- In fact there is reportedly a Wainman shopping mall and Wainman avenue in Nottingham. There was also a Wainmans Nursery which became Wykes Nursery in the mid 1930's.
What I would really like to find out more of are the German roots to the name. I have not found much in this regard but have heard that the german Wainman family abdicated to the UK and have some links with Scotland...