This package looks awesome. It must have been a lot of work to write. My vote is not conditional, but I have some feedback after reviewing the code:
1.) Why not Services_OpenStreetMap with CamelCase?
2.) Have a package-specific InvalidArgumentException subclass.
3.) Way::osmChangeXML() method name is confusing. Maybe Way::amendXML() or Way::amendChangeXML()?
4.) Class docs should have @throws tags where appropriate.
5.) @access tags should be removed since this is PHP5 code.
6.) Some files use a mix of under_scores and camelCase for variable names. (ex. Config.php). Should consistify this. I'd opt for camelCase.
7.) Some method names use Xml and some use XML. Should be consistified.
8.) Criterion::__construct needs better docs. I have no idea how to use it by reading the code.
9.) Package.xml says this requires 5.3. I couldn't see anything obvious that would prevent it from running in 5.2
10.) The custom autoloader should be optional. As far as I remember, PEAR1 code should still use require_once statements. If an autoloader is used, it should be optional in case projects are using their own PSR-0 capable autoloader.
11.) There are some very small issues that could be picked up with phpcs.
12.) I like how the package can support multiple API versions.
13.) Thanks for writing tests already!