It would seem, if you compile for .net 3.5, you would need the .net 3.5 framework installed on the target platform (for the BCL) as well, but you may not because it all runs atop the same CLR 2.0.. I would suspect that you would at least need to make sure that .NET 2.0 SP1 is installed on the target platform. Just to be on the safe side, I will be recommending to my end users that they install the latest framework, although I have not yet researched a method to verify if they have.
Moving from VS2003(.NET 1.1) to VS2005(.net), changed the CLR, which was probably the reason for your “situation”