Ethiopia was and is not Catholic to begin with. It belongs largely to the Monophysite or, better said, Miaphysite strain of Christianity, as a part of the Coptic church. Ties that mattered were with Egypt. That ties were mantained, all along the time Egypt was under Muslim rule, without structural problems (but with occasional crises) even when the Coptic Pope (not to be confused with the Roman Pope) was essentially an important figure within the court of the Muslim rulers of Egypt.
Also, your map is inaccurate in a very important way: the majority of peasantry in the Muslim ruled areas after the first conquests remained majoritarily Christian, Jewish or Mazdeist for a long time. Conversion was often a long process, that took centuries in some places. Muslims had usually little problem about tolerating Christians wherever there was not a political conflict with a Christian power, and often even in that case.
Ethiopia of course clung to Christianity also because it was surrounded by Muslims. However, actual serious Muslim attemps to conquer it came fairly late AFAIK.