It normally takes a couple of months for the reactions to be very noticable, but it does depend on how bad your reactions to eating wheat was when it was in your diet.

The problem of serving staff forgetting that things are covered in breadcrumbs or similar is something I've come across in the past as well; to the point that if I order up a goats cheese salad that I'll ensure that the person I'm ordering from really does understand that the round of cheese shouldn't have breadcrumbs on it. The problem is often that the cheese comes ready prepared with the breadcrumbs already on it :(