Found while looking up other things. From an 1899 newspaper:

Sept. 14, 1535, when Jacques Cartier arrived with three armed vessels; and the story goes that as they turned the point below, and the wonderful rock came in view, the pilot of the leading vessel exclaimed in Bretagne French. "Que beck!" (Quelle beck — "What a peak!") It is a venerable chestnut, but, as no one can give any better reason for the oiigin of the name, we shall have to accept it.

http://www.etymonline.com/index.php?term=Quebec