I've had issues with .NET CF on some of my CE 5 and 6 devices. However, I usually only get the latter error message. The only answer I've found to that is to install the program - and its subfolders - into the same folder where the .NET CF runtime files are, which would be \Windows if the runtimes are preinstalled on the device. However, even then many programs still don't work. Anyway, I doubt that's your problem here.
I'm wondering which .NET CF version is enabled in the registry. I'm guessing that the program requires .NET CF 3.5, and maybe 2.0 is enabled on the device since that's what comes natively with CE 6. If you're familiar with registry editors, try this:
http://pocketnow.com/how-to/tutorial-how-to-upgrade-to-microsoft-net-compact-framework-35