ReCaptcha is currently working here at UBBCentral, on the New User page; I attempted to test this at your site, but it appears that you've disabled it. I am not seeing any outages listed at:
http://www.isitdownrightnow.com/recaptcha.net.htmlhttp://downdetector.com/status/googlehttp://www.websitedownup.com/recaptcha.netAs for the built in libraries, as long as the captcha image displays in the Control Panel selection, it should display for your users (as it utilizes the same coding).
Make sure that your users aren't blocking Javascript, or see if they're using a security plugin that'd block 3rd party (offsite) scripts.