My knowledge of cocktails is based much more on theory than experience ( I love cocktail books), but when someone mentions the word Martini, I think of gin with a bit of vermouth and an olive. I believe a previous poster was right about a gin/vermouth cocktail with an onion being properly called a Gibson, but if the OP's waiter didn't recognize "martini," he definitely wouldn't have recognized that. I guess with the popularity of vodka martinis, one has to specify gin now.
Any cocktail glass drink can be served on ice, but normally one would specify "on the rocks" and it would be served in an old fashioned glass. I get Grasshoppers served that way, because they are too rich on their own (equal parts Creme de Menthe, Creme de Cacao, and cream).