В современном русском языке морфемный состав слова обыденность такой: корень обыденн- и суффикс -ость, у слова обыденный – корень обыденн- и окончание -ый (см.: Тихонов А. Н. Морфемно-орфографический словарь русского языка. М., 1996). Что касается истории этих слов, то первоначальное значение обыденный в древнерусском языке – 'сделанный в один день'; 'однодневный'. Слово происходит от сочетания *об-ин-день 'в один день', где ин < инъ 'один' (ср. др.-рус. инорогъ 'единорог'). Значение 'повседневный' у слова обыденный появилось позже. Сейчас корень -ден- у слов обыденный, обыденность уже не выделяется.
Вы правы, корректно слитное написание. С существительными, прилагательными, наречиями на -о не пишется слитно, если слово с не можно заменить близким по значению словом без не (в данном случае, как Вы верно указываете, – простой, обыденной). Такая возможность как раз и говорит о том, что не – приставка, образующая особое слово.