Why should your legs give out way before your heart gets up to a training rate, aerobic base or not? After all, your legs have a base conditioning too, right? Not the same as cycling, but certainly they are well toned. I'm wondering whether you are mashing at very low cadence, which could be very tiring for a novice cyclist. If your cadence would be 90-100 rpm, your heart rate will be more elevated than for the same power output at 60 rpm, AND your legs would not be nearly as stressed at that power output. If you are pedaling more slowly than 90-100 rpm, give a higher cadence a try and see if it helps.