В сезонах 2002 и 2003 годов перед молодежной сборной стояла двоякая задача. Нужно было выходить из отборочной группы чемпионата Европы 2004 года и одновременно пробиваться в финальный турнир Олимпийских игр в Афинах. Руководство РФС придавало большое значение выполнению этих задач и затеяло своего рода эксперимент, заключавшийся в том, что главный тренер молодежной (а, значит, и олимпийской) сборной Андрей Чернышев являлся одновременно и помощником главного тренера основной сборной Валерия Газзаева. Игроки при этом зачастую тасовались, как колода карт, переходили из одной сборной в другую, и в целом эксперимент нельзя было признать удачным, что впоследствии признал и сам Чернышев.
Денис Колодин попал на карандаш тренерам ещё перед началом отборочного цикла, успев сыграть в товарищеском матче со шведами, выйдя на замену минут за 20 до конца матча. Впоследствии из трех осенних матчей сборной он сыграл в двух, выходя на замены в конце игры. Все три первых поединка наша сборная выиграла. В межсезонье сборная провела три игры, две из которых – со второй сборной США и первой сборной Словении. С американцами наши ребята сыграли вничью, уступив в серии послематчевых пенальти, а у словенцев, предводимых Заховичем, Рудоньей и Ачимовичем, выиграли – 1:0. В обоих матчах Колодин отыграл все 90 минут, как и во встрече с Египтом, которому «молодежка» уступила 2:1. Это было первое поражение команды Чернышева, но, к сожалению, далеко не последнее. Потом были уверенные победы над албанцами в отборе ЧЕ в Тиране со счетом 4:1 и над финнами в товарищеском матче - 3:0. Сборная уверенно лидировала в группе, и казалось, что уже ничего не помешает ей занять первое место.
Но все изменилось в заключительной части сезона. Три поражения подряд: дважды от швейцарцев и один раз от ирландцев, и перед последней встречей с Грузией остается надеяться только на фантастические стечения обстоятельств. В результате победа не приносит радости - ни на чемпионат Европы, ни в Афины наша молодежная сборная не поехала. Денис Колодин сыграл за два сезона в молодежной и олимпийской сборной 7 официальных матчей и 5 товарищеских. Восемь матчей он провел полностью, в четырех выходил на замену в конце встречи.