Speed limit is indeed above speed that 737 can fly (see addendum), but it's not only reason why GPS sometimes doesn't lock. On the plane your phone doesn't get assisted GPS, where rough location calculation is based on ground data like WIFI networks and GSM towers, so time to first fix takes significantly longer because your phone only has access to L1 frequencies. Since it takes a while, 30s for entire satellite message to be transmitted, it's coordinates and the like, and there's no help from ground stations for crude calculation combined with speed of the plane it all ends up contributing to a significantly longer time to first fix or perhaps even problematic fix in the first place.

So all in all, speed contributes to the problem. Yes signal was present at all times. And no, speed is not the sole factor but contributes a lot. GPS chips have improved quite a bit over the time so some old devices will definitely have a problem finding location on plane. Newer ones won't, especially considering they have access to other networks like Galileo, GLONASS and BeiDou.

All GPS receivers capable of functioning above 60,000 ft (18 km) above sea level and 1,000 kn (500 m/s; 2,000 km/h; 1,000 mph), or designed or modified for use with unmanned missiles and aircraft, are classified as munitions (weapons)—which means they require State Department export licenses.[126] This rule applies even to otherwise purely civilian units that only receive the L1 frequency and the C/A (Coarse/Acquisition) code.

Edit: What airplanes have on board, is access to different frequency which your device doesn't. It's not comparable.