At what time(s) and for what reason(s) did people stop referring to Britannia as Britannia and start calling it Great Britain? And if it was referred to as something else between those times what would that be and why?
The term Britannia is the Latin term for the Island. The Greek writers Diodorus of Sicily (Bibliotheca Historica, written between 60 and 30 BC) and Strabo (ca. 64 BC - 23 AD) quote the explorer Pytheas (ca. 325 BC) and refer to it as Prettanikē and νησοι Βρεττανιαι (British islands).
From Caesar onward, the term is fairly fixed in Latin usage as Britannia, first for the whole island, then for the Roman Province extending to Hadrian's wall.
The term re-entered English Language usage through the Old French word Bretaigne, and specifically 'Great Britain' emerged as a way of referring to the island in contrast to Brittany. The Act of Union in 1707 united the Kingdom of England (at that time including Wales) with the Kingdom of Scotland, to produce the Kingdom of Great Britain. A further act of Union in 1800 included Ireland so that, from 1st January 1801, it became the United Kingdom of Great Britain and Ireland, 'Great Britain' indicated the Kingdom including England, Wales, and Scotland as a single entity. This changed again with the secession of the Irish Free State in 1922 and the subsequent Royal and Parliamentary Titles Act 1927, so that the UK became the "United Kingdom of Great Britain and Northern Ireland".
Edit: Corrected some data on Ireland, see comments below.
The "Great" in Britain simply distinguishes it from Brittany (Bretagne) in northwestern France. The term comes from the French where Brittany is Bretagne and Britain is la Grande-Bretagne. "Great" didn't originally connote anything but that it was inhabited by Britons and bigger than Brittany, another Celtic region.