I was having similar problems programming an attiny12 in-circuit. I could erase, program fuses, etc. just fine, but could never successfully program flash memory. The good news is that when I remove the VTARGET jumper and attach my lab power supply (set to 5.0V) to VTG of the PORTB header I am able to program flash successfully (yea!).
Thanks to Morten for this recommendation, although I'm not sure if buy your explanation about the problem being due to STK500's power supply not being able to source much current. The Vcc line doesn't sag at all during (unsuccessful) programming as viewed on my scope.
Now to the flaming: Morten, you say that "The programmer cannot drive heavy loads, so it's always recommended to power the target separately and open the VTARGET jumper." This is a very helpful suggestion, but so far as I can tell, this recommendation is not in the STK500 manual. (Why not?)
Unfortunately, this seems typical of the Atmel's approach. AFTER you spend lot's of your time trying to figure out what you've done wrong, it turns out that it's not your bug, but Atmel's. My first experience with this was after I made the mistake of designing the 2343 into my board. When the chip would start up, I went to this forum and found discussion of the startup bug with the internal RC oscillator.
Oh yeah, that's a known bug; it's in the errata. I suppose I should be a good boy and read all the errata, but come on, this isn't a minor bug, it makes the part effectively unusable in the scenario most people intend to use it in (internal RC oscillator). In my opinion, the part shouldn't even be sold, or if it is, the spec should spell out, in bold type, that the internal RC oscillator doesn't work, practically speaking. I guess experienced AVR developers know to search the message boards
By the way, what is the story with the ATTiny22 replacement part? After I found out about the 2343 oscillator problem, I called Atmel here in CA and spoke to someone introduced to me as the AVR marketing (product?) manager. He said, "ATTiny22, Oh that's been obsolete for over a year." !! Is this true? As far as I can tell, it's impossible to get any--anyone else been able to? Given the lack of availability of this part, I'm just very lucky that my code will work in a Attiny12, with a few features removed.
The bottom line for me is that Atmel doesn't have a whole lot of respect for the time of the people who actually design their MCUs into products. Dear Morten, bless his heart, can't be expected to singlehandedly support the entire AVR development community. On the other hand, maybe this will become a more manageable job now that Microchip has a 8 pin flash MCU ( PIC18F0XX ).