Но он в это время сидел в сосульке же
C чего ты взял? То, что во вступительном ролике ВотЛК он встает с трона не значит, что нам показывают сюжет непосредственно событий текущих. В кадре с армией нежети, идущей строем, внизу отчетливо видна низина по которой оные идут, и там нет ни одной постройки нежити, которая как раз присутствует на момент событий начала аддона. Мост в Редридже строили 2 аддона, а тут весь континент надо оборудовать как времянками, так и заставами с полноценными фортификациями, не говоря о наборе новой рекрутской базы, так что наличие вполне себе говорящего Артаса ровным слоем ложится в логику повествования. Даже активное начало деятельности КТЗ вполне с этим совпадает.