Running on an XP machine (even with .NET 3.5 SP1 installed) I was not able to get any of the other solutions listed here to work.
However working from the same post by Charles Sterling that Davy Landman references, I finally succeeded with this variation:
- Run the .NET 2.0 Configuration tool (Settings... Control Panel... Administrative Tools... .NET Framework 2.0 Configuration)
- Click down to "My Computer ... Runtime Security Policy ... Machine ... Code Groups ... All_Code"
- Create a new code group with membership condition of "Zone"="Local Intranet" and assign the permission set "FullTrust"
- Restart Visual Studio
After these steps I am able to run tests, including after restarts and rebuilds.
EDIT: as described in this answer, you may need to install the .NET SDK (which is different from the .NET framework) in order to have the .NET 2.0 Configuration tool on your system.