The Lubavitcher Rebbe answers that we will need the Cities of Refuge for all the people who have killed inadvertently over the course of exile. They will need to go to the city of Refuge to protect themselves from the "blood redeemer" (Go'el Ha-dam). See there for the explanation of why the "blood redeemer" taking revenge is not incompatible with the Days of Moshiach.
AskMoses.com adds that at the beginning stages of the Messianic Era (see Shaloh mentioned herehere), before the Resurrection of the Dead, the Cohen Gadol can still die, thereby freeing the accidental murderers from the Cities of Refuge.