I've personally been using BSON[1] as a binary alternative to JSON, and it's worked out great. I've written an Objective-C wrapper around the C lib, in case anybody's interested. Every other language has a solid implementation from 10gen (the MongoDB guys). It's a solid format with a clear spec that's extensible and fully supports UTF-8.

[1]: http://bsonspec.org/