In general, I think that protobuf and python-protobuf versions must match, or at least that the bindings are newer than the library itself. Specifically, I've encountered this exact error with using protobuf 2.3 and python-protobuf 2.2. If you are experiencing this problem, please check if this is the case on your system and report back.
-- Regards Jon Nordby - www.jonnor.com
