Has there been some change in the varieties of broccoli sold in US supermarkets in the last few years?
First, there can be a difference in varieties that are sold in supermarkets. Calabrese, which is a member of the broccoli family, is what is most often sold in grocery stores. The other variety that may be found is 'Italian Green Sprouting'. (Note that I am not referring to other types such as broccoli rabe, broccolini, etc., but just what we think of as 'regular' green broccoli.)

From  seedaholic.com :


  Calabrese &amp; Broccoli is a confusing series of plants: 
  Supermarkets have helped to confuse the issue of what is broccoli and what is a calabrese by calling both by either name. Most ‘Broccoli’ sold in the supermarkets is actually Calabrese not broccoli.
  
  Broccoli has small heads (mainly purple, sometimes white or green) which mature slowly and can occupy the ground for almost a year. (The word broccoli means 'little sprouts' in Italian). Calabrese are smaller plants that produce larger crowns. 
  
  Keep in mind is that broccoli is an over wintered crop but calabrese produces its crop the same year before winter. Sprouting broccoli can be harvested from late winter to late spring. Calabrese can be harvested from mid-summer to mid-autumn. If you grow both calabrese and sprouting broccoli, your kitchen will be kept in broccoli for most of the year. 
  
  To add to the confusion, this variety, called "Italian Green Sprouting" is a "heading" broccoli. The name refers to the multitude of sprouts it produces once the main head is harvested.


Next, and what may be an even larger factor, is how it is stored on its way to market or production and in the store. I would suspect that this may well be the source of your issue. From  farmtotable.colostate.edu :


  Safe Storage and Handling
  
  Broccoli should be stored unwashed, in loose perforated bags in the refrigerator. Broccoli left unrefrigerated will quickly become woody and fibrous. Wet broccoli can become limp and soggy as well as support the growth of microorganisms, so wait to rinse it until just before eating.


And...


  Why is my broccoli so tough and chewy?
  
  At room temperature, harvested broccoli will convert its sugar into a fiber called lignin. The more time spent at room temperature, the more lignin is produced and the more fibrous your broccoli becomes! Keep your broccoli refrigerated to extend the shelf life.