Check privileges. Is there any unnecessary privileges or you missed any privileges which is needed for your app.
If you think you have generated the certificate appropriately, the right click on the device id from connection explorer and click "permit to install".
If you still face the problem, remove all the certificates you have created. You may follow this guide carefully. I think, the problem is with certificate type.
Please make sure you have installed Samsung certificate extention from Package Manager.
And you have created Samsung certificate not the Tizen certificate.
Addendum:
If the Samsung Certificate Extension is not showing up in the Extension SDK-Tab it must first be enabled in the Package Manager - Configuration, accesible via the tools-icon.