Can food spoil at cold temperatures?
It depends on what you mean by "spoil". 

The purpose of the fridge is to prevent food from growing pathogenic organisms. There is a clear dependence there: The colder the environment, the slower food gets "spoiled", or unsafe to eat. 

But we also want our food to be tasty. And cold temperature does change the texture and taste of some foods, especially fruit and vegetables. If it stays above freezing, some of them still get unpleasant, especially tomatoes and tropical fruit. The worse problem is if the temperature gets below freezing. Then everything turns mushy and unpleasant. And because fridges do not have a very precise temperature control (due to imprecise sensors but also to the fact that the temperature and humidity varies throughout the space of the fridge), a thermostat set too high can lead to temperatures below freezing at least in some parts of the fridge, rendering some vegetables, specifically green salads, practically inedible. 

On this one, I side with your roommates. I have never seen a fridge which had it necessary to turn the thermostat all the way up. Milk and cooked food does great at temperatures just below 4 degrees C, which for most fridges I've seen corresponds to a middle setting. Expiry dates are based on this temperature. Cheese actually prefers higher temperatures, like 15 degrees, people just keep it in the fridge because they lack a better space in a typical kitchen. Setting the thermostat on the highest setting gets the fridge around, sometimes even below, the freezing point, and yes, it makes it impossible to keep vegetables in the fridge (I've seen them turn bad in the closed vegetable drawer too), and wastes lots of energy besides.