Lynden Barber from Sydney Morning Herald said the album "sets a new standard of maturity for Australian pop" adding "A New Kind of Blue is a record that takes some time to smoulder its way into your affections, but once there, it glows like embers on a winter's fire. This is suave, adult music that bears the intimacy of confessions whispered in the early hours. Australia – or anywhere else, for that matter – is unlikely to hear a record as gracefully accomplished in the whole of 1989."
Clinton Walker from Rolling Stone Australia gave the album 4 out of 5 saying "A New Kind of Blue is luscious. Even when the melodies aren't arresting in their own right, Cummings knows, and uses well, the power of the gospelesque chorus, to lift them. The instrumentation and arrangements – mostly by O'Mara – are discrete and tasteful to a tee, and Cummings' tenor has that almost cracked, smokey allure."