Леттерман старался побыстрее завершить интервью, но Мадонна не собиралась уходить. «Дай мне высказаться, Дэвид. Не надо выставлять меня дурой», — сказала она резким тоном. Скандал был обеспечен. Мадонна тринадцать раз употребила слово «fuck», разнообразно обозвала Дэвида, а также зрители услышали ее мнение о том, каково писать в душе. На следующий день газеты пестрили сообщениями о Мадонне. Говорили, что она выжила из ума и «делает карьеру, прибегая к недостойным средствам». Популярность ее снова упала до критической черты. Многие осуждали Мадонну за «интервью с тринадцатью матерными выражениями», забывая, что Леттерман в известной мере спровоцировал ее, задавая скользкие вопросы о сексуальной жизни. Ее просто понесло. В тот вечер, когда она стала национальной антигероиней, Мадонна вела себя как раненый зверь, напомнив своими едкими высказываниями панк-рокера Стива Джонса, который в 70-х годах в английской прайм-тайм-передаче обозвал ведущего «мерзким мудаком». «Я рад, что ты смогла прийти и облить всех нас грязью», — сказал ей Леттерман. Мадонна понимала, что выставляет себя не в лучшем свете, но чувствовала себя уязвленной и сорвалась. Спустя несколько лет она пояснила: «Это был такой период, когда я испытывала ужасную злость. Злость на свое воспитание, на наше сексистское общество. Злость на то, что во мне видели лишь сексуальную женщину и отказывались видеть талант. Меня бесило просто все».
Когда шумиха улеглась, Мадонна постаралась реабилитироваться. Она выступила в шоу Джея Лено, где вела себя довольно сдержанно, и на церемонии награждения MTV публично помирилась с Леттерманом. Но все же единственно верным способом вернуть расположение людских сердец для нее оставалась музыка.
Мадонна вновь обосновалась в студии, продолжая разрабатывать музыкальное направление, заданное альбомом «Erotica». Время, когда она задумала записать «Bedtime Stories», было периодом восхождения R'n'B. Джанет Джексон стала более продаваемой, чем ее братец, Тони Брэкстон сделалась мировой знаменитостью, а сингл «Whatta Man», совместное произведение коллективов «Salt 'N' Рера» и «En Vogue», оказался одним из главных событий года. Палитру дополняли Мэри Джей Блайдж и хип-хоповая группа «TLC». Музыка всех этих исполнителей использовалась Мадонной в качестве ориентира. Хаус-ритмы Шепа Петтибона ушли в прошлое. «Мне хотелось добиться R'n'B-звучания… У меня есть своя характерная манера исполнения, и идея заключалась в том, чтобы наложить мой вокал на хип-хоповую музыку так, чтобы в итоге получился, так сказать, фирменный диск от „Madonna record"», — говорила она.
Вначале она провела ряд встреч с продюсерами хип-хопа, одним из которых был Кеннет «Бэйбифэйс» Эдмондс, сотрудничавший с такими исполнителями, как Уитни Хьюстон, Тони Брэкстон и «TLC». Мадонне хотелось, чтобы новый альбом был более романтическим и «понятным», чем «опередивший время» «Erotica». Их совместным с Бэйбифэйсом детищем была трогательная любовная баллада «Take A Bow», занявшая первое место в американских чартах. По сравнению с остальными треками альбома эта композиция кажется немного приторной, но сингл с успехом продавался по всему миру. Менеджер Бэйбифэйса Рамон Херц вспоминает, как Мадонна исполняла ее на фестивале в Сан-Марино. «Пока мы не приехали туда, я даже не представлял, насколько популярна Мадонна. Мы ехали колонной: я, Мадонна и Кении (Бэйбифэйс) впереди, на „мерседесе". Городок маленький, и в нем творилось настоящее столпотворение. Улицы были переполнены людьми, и со всех сторон раздавались крики: „Мадонна! Мадонна!" Так приветствуют только Папу Римского. Мы едва сумели проехать. Кении сказал: „Они еще не знают, кто я такой", — и все засмеялись».
Мадонна чрезвычайно щепетильна в вопросах этики. Когда дело дошло до исполнения «Take A Bow», она проследила, чтобы Бэйбифэйс стоял рядом с ней. «На репетициях он обычно стоял позади нее, на помосте, а тут она поставила его рядом с собой, как бы подчеркивая, что они вместе. Это было данью уважения. Такое внимание редкость», — говорит Херц.