Unfortunately, that's the nature of Alpha-Cellulose, which is one reason why I avoid any paper that uses it as a base. 100% cotton papers are very easy to write on with a pencil. Have you tried a very soft leaded pencil?
It's not the alpha-cellulose base sheet nor the traditional sizings applied during the paper making stage that's the culprit here. It's the very funky anti-curl coating applied to the verso of Canson Baryta Photographique (and it's rebranded counterparts) which doesn't provide proper tooth for writing with pencil. To underscore this point, many writing papers on the market today are comprised mainly of alpha cellulose rather than 100% cotton, and they are intended to be written on with either pen or pencil.
Due to the nature of the back coating on Canson Baryta Photographique (and this holds to for the newer version II as well) one will need to use pigmented pens like Sakura Pigma Micron, Staedtler Pigment liner, or even a permanent dye marker like Staedtler Lumocolor to write on the verso of any inkjet papers with polymer type anti-curl coatings. These media include most if not all RC photo papers as well. FWIW, the Staedtler LumoColor pens seem to dry fastest and adhere with less smudging on plastic surfaces compared to most pigment based pens.
Other fine art media with an alpha-cellulose base takes a #2 pencil quite well, for example, Hahnemuhle Fineart Baryta Satin because they retain much more of the sized paper surface on the verso compared to Canson Baryta Photographique and its look-alike competition.
cheers,
Mark
http://www.aardenburg-imaging.com