This should not be put in the versionadded directive, instead put a caution directive after the into paragraph:

..caution::    This requires PHP 5.5 or ...

And are there any reasons you based this on 2.3 and not 2.2?

Yes, version 2.2 did not require PHP 5.5 for bcrypt encoding but now 2.3 does

For more info, in Symfony 2.2 it would try to use the password_hash function (available in PHP 5.5) if it didn't exist, it would fall back to an internal function to create the crypt. In 2.3 the fallback functionality was removed and now completely relies on the password_hash function and throws an exception if not found.
Here is the PR that removed the functionalitysymfony/symfony#7853

What I don't understand is why this BC break (especially considering 5.5 isn't even released yet) wasn't documented in the update notes, as people shouldn't have to go hunting for that info.

@masterkaos The bcrypt encoder can still be used in PHP 5.3 or 5.4 thanks to the password_compat library, as highlighted in this PR. this library is implementing the password_hash function in PHP for people not using 5.5 yet.
And we switched to it to avoid maintaining the bcrypt code ourselves again (especially as there was some issues in the implementation compared to the password_compat library).
And this is documented in the changelog of the security component:https://github.com/symfony/symfony/blob/2.3/src/Symfony/Component/Security/CHANGELOG.md#230

I did eventually see it in the security changelog, but it would be nice if all of the changelogs would be aggregated to or linked fromhttps://github.com/symfony/symfony/blob/master/UPGRADE-2.3.md

Seems like it is too easy to miss something having to go through a bunch of different components looking at all of the changelogs independently, but I will keep that in mind for the future. And I realize it still can be used, but doesn't work "out of the box" < 5.5. A couple additional BC breaks I missed was a few other deprecated methods that were removed in 2.3 that were mentioned in the 2.0 to 2.1 upgrade notes but not in 2.2 to 2.3. (Mainly the twig field_* to form_*), and these twig functions did not appear in the deprecated section of the debug toolbar, however I admit this was my fault