I have a Samsung Captivate, running the stock Froyo ROM, rooted. When I try to install a large app from the Market, I get the error "insufficent space on the device", for apps of ~40 MB, with 700+MB free. I first noticed it with "Jelly Defense" on Google's Christmas-week sale, but you can see it for yourself if you try the free "Reiner Knizia's Labyrinth" which is also quite large.
This is a common problem -- just Google it and you'll see dozens of posts around the Internet going back almost a year. From those posts, I've tried two free apps that are supposed to help, "Market Fix" and "Cache Fixer", but neither has done the trick yet. As I understand it, both are supposed to re-mount /cache as a loopback file on the SD card. I don't know why they don't work. If anybody has fixed this specifically on the i9000 series (SGS1, Captivate, Fascinate, etc), please let me know how!