¿Cómo anido una promesa dentro de otra función de promesa en node.js?

Rodeando todo por una new Promise La llamada no ayuda en nada. Dentro de él, todavía tendrías un infierno de devolución de llamada. Y no, lanzar Promise.resolve() en una función que no devuelve nada tampoco ayuda.

Deberá prometer las primitivas asíncronas, es decir, las partes más pequeñas que son asíncronas. En tu caso, eso es distance.matrix y connect de mongo +insert :

function getMatrix(m, o, d) {
    return new Promise(function(resolve, reject) {
        m.matrix(o, d, function(err, distances) {
            if (err) reject(err);
            else     resolve(distances);
        });
    });
}

function save(url, store, k) {
// cramming connect+insert in here is not optimal but let's not get into unnecessary detail
    return new Promise(function(resolve, reject) {
        MongoClient.connect(url, function(err, db) {
            if (err)
                reject(err);
            else
                db.collection(k).insert(store, function(err, results) {
                    if (err) reject(err);
                    else     resolve(results);
                    db.close();
                });
        });
    });
}

Ahora que los tenemos, podemos usarlos y combinar nuestras promesas en lo que realmente está buscando:

module.exports = Promise.all(dep.map(function(name) {
    distance.departure_time(name);
    return getMatrix(distance, origins, destinations).then(function(distances) {
        if (!distances) throw new Error('no distances');
        var promises = [];
        if (distances.status == 'OK') {
            for (var i=0; i < origins.length; i++) {
                for (var j = 0; j < destinations.length; j++) {
                    var origin = distances.origin_addresses[i];
                    var destination = distances.destination_addresses[j];
                    if (distances.rows[0].elements[j].status == 'OK') {
                        var duration = distances.rows[i].elements[j].duration_in_traffic.value;
                        var myobj = {
                            destination: destination,
                            departure_time: name,
                            duration: duration
                        };
                        var str = destination.replace(/[,\s]+/g, '');
                        promises.push(save(url, myobj, str));
//                                    ^^^^^^^^^^^^^^^^^^^^^
                    }
                }
            }
        }
        return Promise.all(promises); // now wait for all save results
    });
}));