В Python 2.7 или 3.1 вы можете использовать OrderedDict:
from collections import OrderedDict
from operator import itemgetter
tel = {'jack': 18, 'sape': 4139, 'sar': 2139, 'mape': 319, 'sipe': 29}
newtel = OrderedDict(sorted(tel.items(), key=itemgetter(1), reverse=True))
Дополнительные примеры можно найти в Что нового документ.
РЕДАКТИРОВАТЬ: теперь используетсяitemgetter вместо лямбды, чтобы порадовать тех, кому небезразлично.Прошу прощения у тех, кто нашел это более понятным по-старому.