I had this same issue with my used Haier kegerator I picked up on craigslist ($50 including two full CO2 tanks!). I ended up throwing a small fan inside the kegerator to circulate the air and it has made a huge difference. Before I did that, I could not get the temp below 40 even on the coldest setting. Now I have it at just below the warmest setting and its around 36-38 degrees. And there is no more ice/frost build-up on the cooling plate in the back.