EDIT
The code below only changes the tiles and does not impact routing. See MapQuest directions web service on how to use JavaScript to get routing data from their Route Service.
According to this blog post, you just need to change the preamble.
The Cloudmade maps layer looks like this.:
var map = new L.Map('map');
var cloudmadeUrl = 'http://{s}.tile.cloudmade.com/API-KEY/997/256/{z}/{x}/{y}.png',
cloudmadeAttrib = 'Map data © 2011 OpenStreetMap contributors, Imagery © 2011 CloudMade',
cloudmade = new L.TileLayer(cloudmadeUrl, {maxZoom: 18, attribution: cloudmadeAttrib});
Change the preamble to.
var map = new L.Map('map');
var mapquestUrl = 'http://{s}.mqcdn.com/tiles/1.0.0/osm/{z}/{x}/{y}.png',
subDomains = ['otile1','otile2','otile3','otile4'],
mapquestAttrib = 'Data, imagery and map information provided by <a href="http://open.mapquest.co.uk" target="_blank">MapQuest</a>, <a href="http://www.openstreetmap.org/" target="_blank">OpenStreetMap</a> and contributors.',
mapquest = new L.TileLayer(mapquestUrl, {maxZoom: 18, attribution: mapquestAttrib, subdomains: subDomains});