Правильно: уланудэнец (и уланудинец). Правило таково: пишутся слитно существительные – названия жителей, образованные от имен собственных, пишущихся через дефис, ср.: ньюйоркцы, ореховозуевцы, костариканцы, санктпетербуржцы, устькаменогорцы и т. д.
От склоняемости/несклоняемости наименования города написание названия его жителей никак не зависит.