Why are tropical cyclones forming earlier in the North Atlantic basin?
The shift appears to match up to a large change in the number of cyclones that peak as tropical storms in the early part of the TC season (here defined as March-July), shown by the blue (tropical storms) versus purple (hurricanes) in this graph (made using the HURDAT2 dataset from NHC):



It appears that a large part of the increase in tropical storms lines up with a coincident decrease in tropical depressions (shown in green).
It's notable that tropical depressions only start appearing in the dataset starting in 1963.  I don't know it for a fact, but because the timing lines up with the advent of satellite weather data it suggests TDs may have been added once satellite offered a better picture to find and analyze weaker systems.
Therefore, it would seem one possible theory might be that there was an initial predilection to hold less organized systems at tropical depression status, but as data has increased from hurricane hunters, satellite resolution upgrades, and additional/more rapid data reports, more of these systems were progressively graded as tropical storms.

Looking into the data at full resolution, it appears the trend may be greatest in weak and moderate tropical storms (focus on the lesser change in dark blue colors, and in most of the pink bands):





Does this pattern also match the rest of the year?

I'd suggest yes and no.  Here's the corresponding graph for the late parts of the season:



So it looks like:


Tropical storms are still on the upswing in the late season, just not nearly as much (the trend line for early season goes from 0.5 to 2.5, for late season it goes from 1 to 2).
Cyclones maxing as tropical depressions have also sharply dropped away in the late season, closely matching the early season pattern (indeed, late season TDs were less to start with, in parallel with the smaller TS increase).
Also note that the number of hurricanes themselves have increased in the late season by over 50% (while remaining fairly constant in the early season).


You can look into the trends in each storm type in the following set of graphs:  

TD/TS/HUR 50 years: early, mid, late, total
TS/HUR 100 years: early, mid, late, total
By strength full history: early, mid, late, total
(Note these analyses don't include 19 unnamed TCs in 1967-69 where no intensity is given in HURDAT)



Many certainly do propose climate change as a possible mechanism to shift the intensity and numbers of TCs.  Quite a few warming modeling studies have suggested there would be an increase in tropical storms.  It appears that this paper (Kunkel et al 2009) has some interesting discussion into the topic in the hurricanes and typhoons section.  The conclusion of:


  In summary, robust detection of trends in Atlantic and western North
  Pacific TC activity is significantly constrained by data heterogeneity
  and deficient quantification of internal variability. Attribution of
  past TC changes is further challenged by a lack of consensus on the
  physical linkages between climate forcing and TC activity. As a
  result, attribution of any observed trends in TC activity in these
  basins to anthropogenic forcing remains controversial.


seems to offer a fair reflection of the overall situation as of now in tropical cyclones and possible connections to climate change.  There's certainly plenty of debate over how significantly climate change is influencing the shifts seen; some will draw more conclusions than others.

Regardless of whether it's due to changes in identification practices or other causes like human climate change, it's clear there are more named systems in the early season, and that would certainly often result in an earlier first name.

On the other hand, is it due particularly to sufficient ocean temperatures existing earlier in the season over wider areas?  It would seem odd that such a change would mostly impact only the number of tropical storms, and not change the number of hurricanes.  But further analysis should certainly be done and the other MPI factors.

I do offer one final small postulate, based both upon these graphs and upon my own perceptions... perhaps at least a small part of the upswing in tropical storms might be due to an increase in the buzz at the start of each new year.  It seems there is more and more talk and "excitement" and interviews as each year get started.  And I wonder if that may prime forecasters to make earlier designations sometimes.