/MDd is the debug library. libprotobuf.lib only links against it when built in debug mode. Are you also compiling your app in debug mode? You need to make sure to compile both projects in the same mode.
Are you able to build the tests that come with the protobuf code? If so, maybe check what's different between the tests project and your project.
Otherwise, I don't have any other ideas.