Должна или нет УК выдать новые ключи всем собственникам квартир?

Все зависит от того, как оформлены отношения по пользованию кладовкой в подвале МКД и как определить возможность ее использования как самостоятельного помещения или нет.

Как правило, если это частные кладовки, то это исключает возможность отнесения этого помещения к общедолевой собственности собственников помещений многоквартирного дома. Следовательно, данное имущество должно быть оформлено в собственность конкретному лицу.  

По общему правилу, в силу статьи 289 Гражданского кодекса Российской Федерации собственнику квартиры в многоквартирном доме наряду с принадлежащим ему помещением, занимаемым под квартиру, принадлежит также доля в праве собственности на общее имущество дома (статья 290 Гражданского кодекса Российской Федерации).

На основании пункта 1 статьи 290 Гражданского кодекса Российской Федерации собственникам квартир в многоквартирном доме принадлежат на праве общей долевой собственности общие помещения дома, несущие конструкции дома, механическое, электрическое, санитарно-техническое и иное оборудование за пределами или внутри квартиры, обслуживающее более одной квартиры.

Согласно пунктам 1 и 3 части 1 статьи 36 Жилищного кодекса Российской Федерации собственникам помещений в многоквартирном доме принадлежит на праве общей долевой собственности общее имущество в многоквартирном доме, в том числе помещения в данном доме, не являющиеся частями квартир и предназначенные для обслуживания более одного помещения в данном доме, в том числе межквартирные лестничные площадки, лестницы, лифты, лифтовые и иные шахты, коридоры, технические этажи, чердаки, подвалы, в которых имеются инженерные коммуникации, иное обслуживающее более одного помещения в данном доме оборудование (технические подвалы); крыши, ограждающие несущие и ненесущие конструкции данного дома, механическое, электрическое, санитарно-техническое и иное оборудование, находящееся в данном доме за пределами или внутри помещений и обслуживающее более одного помещения.

Если кладовки не предназначены для обслуживания более одного помещения в данном доме, а являются самостоятельными объектами, то они не могут принадлежать собственникам МКД на праве общей долевой собственности общего имущества в многоквартирном доме. Но и действия УК в данном случае не могут быть признаны законными (если отсутствует опасность несанкционного доступа к инженерным сетям, приборам и т.д. МКД), т.к. УК никакого отношения к данным кладовкам не имеет.