W tym samym roku nawiązał współpracę z Alainem Changiem, który zaczął komponować, aranżować i produkować dla niego piosenki.
Podczas prac nad kolejnym albumem nawiązał współpracę m.in. z Amy Foster, z którą napisał utwór „Home” umieszczony na ścieżce dźwiękowej do filmu Clare Kilner Pretty Man, czyli chłopak do wynajęcia (2004). W lutym 2005 wydał album It’s Time, który promował m.in. coverem przeboju Niny Simone „Feeling Good”. Płyta rozeszła się w nakładzie ponad 6 mln egzemplarzy na świecie. Album spędził 72 tygodnie na pierwszym miejscu listy Billboard Jazz Albums. W listopadzie 2005 wydał drugi album koncertowy pt. Caught in the Act, za który był nominowany do nagrody Grammy w kategorii „najlepszy wykonawca tradycyjnego popu”. Tuż przed galą rozdania statuetek w wywiadzie dla „The Canadian Press” wyraził niezadowolenie z powodu nietransmitowania w telewizji rozdania nagród w jego kategorii, jednocześnie zapowiedział bojkot imprezy, twierdząc, że nagrodę i tak otrzyma Tony Bennett. Wyjaśnił: Czemu miałbym iść na rozdanie Grammy?