I just did some investigation and apparently the Byzantine Empire combined Apulia, Bruttium and Calabria into a single province which they called Calabria. The Byzantine Empire then lost control of most of this province, leaving only Bruttium under byzantine control. They still continued to call their province Calabria, which is why the name shifted from the heel to the toe of Italy.

If you speak Italian you might want to have a look at M. Schipa's La migrazione del nome Calabria, in which he investigates the name shift of Calabria.

Since I don't speak Italian myself I had to rely on this [footnote] (http://oll.libertyfund.org/titles/gibbon-the-history-of-the-decline-and-fall-of-the-roman-empire-vol-8?q=calabria#lf0214-08_footnote_nt_047) in Gibbon's decline and fall of the roman empire in which he summarises Schipa's investigation:

I have described the state of Italy from the excellent Dissertation of Beretti. Giannone (Istoria Civile, tom. i. p. 374-387) has followed the learned Camillo Pellegrini in the geography of the kingdom of Naples. After the loss of the true Calabria, the vanity of the Greeks substituted that name instead of the more ignoble appellation of Bruttium; and the change appears to have taken place before the time of Charlemagne (Eginhard, p. 75 [V. Car. 15]). [The change was probably the result of an administrative innovation in the second half of the seventh century (due presumably to the Emperor Constans II.). Calabria, Apulia, and Bruttii seem to have been united as a single province, entitled Calabria. Thus Bruttii came to be part of (official) Calabria. When the duke of Beneventum, Romuald, conquered most of the heel (soon after ad 671) Bruttii came to be almost the whole of “Calabria.” Thus an administrative change, prior to the conquest of Romuald, initiated the attachment of the name Calabria to the toe; the conquest of Romuald brought about the detachment of the name from the heel. These are the conclusions arrived at in the investigation of M. Schipa on La migrazione del nome Calabria, in the Archivio storico per le province napoletane, 1895, p. 23 sqq.]