Companion App Find peer service not found?

Hard to say what is wrong without seeing your code. There are a lot of things they might not work in case sap engine.

Did you add this privilege: http://developer.samsung.com/tizen/privilege/accessoryprotocol to tizen-manfest.xml file?
[edit: broken auto-link has been removed. See Accessory protocol .NET companion app]

Make sure the name is the same as the Android manifest file is. Once I had an issue with that.