Jerseygardengirl, I've always had the same problem. Always planted lettuce some time in late April (around last frost date here in Zone 6b, NJ), never could get them to grow properly.
This year, I started looseleaf lettuce Red Sails from seeds on Feb. 8 on a whim. Planted them out on March 14. Other lettuce -- Iceberg Summertime and Red Glacier, Batavian Magenta, Butterhead Red Cross, Baby Romaine TinTin -- I started on March 1. Some of the Summertime was planted out on March 15. All others including rest of the Summertime were planted out on March 31. They were all protected with plastic covers and/or double layer of floating covers, as well as heavy plastic sheeting surrounding the garden bed fence. I kept a thermometer in each location to monitor low temps as well as daytime temps IN THE SUN.
With all the frost and freezes we had, it was necessary to keep them covered until April 21. Then we had that heat wave with day high hitting the 90's, and I had to shade them and mist them during the day to keep them from overheating.
But I was eating the extra early Red Sails by early April and the other heading varieties all headed up beautifully. I can tell you though, that out of all of them, Iceberg Summertime was the WORST. Slugs regularly had orgies inside it
If you want Iceberg, I recommend you go with Red Glacier.