"Why can a Cohen not marry a convert? When someone converts, they are considered to be completely Jewish - so why the prohibition?"
Excellent question.
Firstly, one must understand the role of the Cohen (Priest). The Torah looks at him, though perhaps less relevant today, as an intermediary representing the Jewish People in their service and devotion to God. They were responsible to conduct the sacrificial offerings and services associated with the holy Temple in Jerusalem. They were involved in special purification rites when necessary. As such, they had to maintain a level of sanctity that was above and beyond the expectations for the rest of the Jewish people.
One important are of sanctity according to the Torah standards is that of sexual propriety. The Torah goes through great lengths to emphasize the necessity for all Jews to maintain purity in their actions, and progeny, to uphold a standard of holiness that transcends anything the rest of the world is required to follow. Accordingly, a cohen is not allowed to marry a Jewish woman who has been intimate with a gentile man. A convert, notwithstanding her personal level of chastity, is assumed to have been intimate and thus unable to marry a cohen. For related reasons, a Jewish divorcee is also not allowed to marry a cohen.
As you can see, the rationale for this restriction has nothing to do with the Jewish status of a convert. It may sound a bit strange because we don't have the Temple services today. However, there is an eternal Jewish hope that it will be rebuilt speadily in our times, and the Cohanim (pl for cohen) must be fit and ready to resume the service.
best,
aaron parry