It appears that Joomla 3.5 has broken ALFContact's reCAPTCHA support.
Working on a solution, in the mean time stick with 3.4.8 if you badly need the reCAPTCHA feature.