To install your application on a Samsung device it needs to be signed with a Samsung certificate profile, not a Tizen certificate profile. In a default install the Tizen Studio certificate manager only creates Tizen certificate profiles. This was the problem in my case.
To enable creating a Samsung certificate profile, start the package manager (in Tizen studio: Tools -> Package manager), go to the 'Extension SDK' tab, expand 'Extras' and install 'Samsung Certificate Extension'.
After installing this, use the Certificate Manager (in Tizen studio: Tools -> Certificate manager) and create a new certificate profile (possibly first delete your existing certificate if you didn't publish anything). Now it'll let you choose between creating a Tizen certificate profile and a Samsung certificate profile. You'll need to sign in to a Samsung account to be able to create a Samsung certificate profile. Make sure that the Samsung certificate profile is the active one when you're done.