Adding the certificate to the solution should resolve what you need.
If it didn't, then most likely the problem IS THE CERTIFICATE.
The certificates created automaticaly by the Visual Studio don't have a full cascade of CA's (Certificate Authorities) and therefore cannot be used as a base for Full Trust Application Certification.
By using then you may notice that your Applications gain a PublicKeyToken to their references instead of "PublicKeyToken=null"; but that is not what qualifies the software as Full Trust.
To do that you need a certificate fully qualified, with a chain os certification and a CA. That CA needs to be on the trust chain. If you here
installing-a-self-signed-certificate-as-a-trusted-root-ca-in-windows-vista you'll see the CA's installed on Windows, and the CA must be there - either because it's a trusted CA native to windows or because you added it manualy (to the client machine).