I have been learning SharePoint from the ground up recently, and one of the hardest problems I have come across is deploying a custom Code Access Security (CAS) policy with my solution package. I'll explain the problem that I encountered, and how I solved it.
First, I started off with an extremely simple web part that did absolutely nothing. I created a solution package with no CAS policy in it, installed it on WSS, and deployed it to my test site. Everything worked just fine; I was able to view my web part in the gallery, and add it to web part pages.
Then I added a CodeAccessSecurity node to my solution manifest. In the policy, I gave my web part the SharePointPermission so that it could access the object model. The install went fine, but after the solution was deployed, I got "System.Security.Policy.PolicyException: Execution permission cannot be acquired." I was very confused because in my mind, my CAS policy should have been granting me an additional permission, not removing any permissions. Moreover, I was not even making any privileged calls, the web part was unchanged and did absolutely nothing.
After asking a lot of questions, reading a lot of articles, and then analyzing the changes in my trust configuration files, I finally discovered that when I added the custom CAS policy, it was granting the SharePointPermission, but it was only granting the SharePointPermission. I then added all of the minimum permissions needed to run the web part in the first place, and then everything worked fine.
So, when you create a custom CAS policy, be sure to include ALL of the permissions that you need, not just the additional permissions.
UPDATE: Below is an example of my CodeAccessSecurity node. It's been a long time since I wrote this and things have changed, but basically I had to add the basic permissions, AspNetHostingPermission, SecurityPermission, and WebPartPermission.
<PermissionSet class="NamedPermissionSet" version="1" Description="Permissions for ArrowWebParts">
<IPermission class="AspNetHostingPermission" version="1" Level="Minimal" />
<IPermission class="SecurityPermission" version="1" Flags="Execution" />
<IPermission class="WebPartPermission" version="1" Connections="True" />
<IPermission class="System.Security.Permissions.FileIOPermission, mscorlib, Version=220.127.116.11, Culture=neutral, PublicKeyToken=b77a5c561934e089" version="1" Unrestricted="true" />