This happened the first time I used Link2SD. If you had any apps linked the FroYo way to the sd card before you took out card and formatted it for link2sd, those apps aren't deleted. I noticed this when I mounted the ext2 partition on my computer and some of the files were "Angry Birds Rio_1", including a "_1" whereas others weren't, eg. "Angry Birds Seasons". The ones with the "_1" were duplicates that the phone wasn't picking up AFAIK.
I just factory restored the phone, reformatted the ext2 partition and started again, setting up Link2sd before installing anything else. I had backed up the apps with Titanium and when I restored them all on the factory restored phone and made sure all were linked, I was only using 50mb of internal storage. If I install Angry Birds and link it, the internal memory is still reduced by ~16mb, even though it is meant to be linked so that could also influence your memory shortage?