Just discovered via some google-fu that we have a Sagem C1000 series meter in the house, which includes
* Interface de télé-information client permettant le raccordement à un système de gestion d'énergie
so, with a bit more googling I discovered that it's 1200 baud, 7 bits one stop. and lo - there's even an arduino shield already made for it!
--- update ---
Have discovered that there are many hacks around to parse this teleinfo - some of which need a licence fee (!!!) and do fancy things like export to bdpv.fr
Sample of the data stream is at http://www.planete-domotique.com/blog/2010/03/30/la-teleinformation-edf