Оччень интересная находка!
Тему об "Илье Римлянине" уже поднимал ale:

http://www.chronologia.org/dcforum/DCForumID14/18.html

Цитата оттуда:
"Илья Муромец родился в Римском царстве. Опровергнуть данное утверждение невозможно, поскольку утверждается сие в русской БЫЛИНЕ. У меня этой былины нет, к сожалению, под рукой; могу лишь дать пространную цитату из статьи И.П.Смирнова в сборнике "Древнерусские литературные памятники. ТОДРЛ, том 33, с. 197":
<<...чужеземным властителям даются русские имена, Тугарин участвует в пиршестве у князя Владимира, Батый обращается к татарам со словами:"Кто умеет говорить русским языком человеческим?"(Киреевский, вып.4,с.39); в то же время РОЖДЕНИЕ ИЛЬИ МУРОМЦА СЛУЧАЕТСЯ В "РИМЫСКОЕМ ЦАРСТВЕ">>.
Александр Малярчук"

Для меня же это стало указанием на Урал - особенно учитывая форму "Римыское царство" (см. подтему "О Рыме и Риме" в теме о Рымнике": http://chronologia.org/cgi-bin/dcforum/dcboard.cgi?az=read_count&om=12984&forum=DCForumID2 ), т.е., вероятно, "Рымникское-Римыское-Рымское-Римское" - примерно об одном и том же.

Ну а принимая тождество "Рым = Рим", связь с Царем Сибирским тут абсолютно понятна...