I had the same issue once on an older steel frame bike. When I looked closely at the nut on the quick-release, I noticed that the "teeth" on the surface of it were worn down and not gripping well. I replaced the skewers with a new pair with a stronger "bite," and the problem was solved.