For anyone else running into this, I had this problem due to my npm installing into a location that's not on my NODE_PATH.

[root@uberneek ~]# which npm
/opt/bin/npm
[root@uberneek ~]# which node
/opt/bin/node
[root@uberneek ~]# echo $NODE_PATH

My NODE_PATH was empty, and running npm install --global --verbose promised-io showed that it was installing into /opt/lib/node_modules/promised-io:

[root@uberneek ~]# npm install --global --verbose promised-io
npm info it worked if it ends with ok
npm verb cli [ '/opt/bin/node',
npm verb cli   '/opt/bin/npm',
npm verb cli   'install',
npm verb cli   '--global',
npm verb cli   '--verbose',
npm verb cli   'promised-io' ]
npm info using npm@1.1.45
npm info using node@v0.8.4
[cut]
npm info build /opt/lib/node_modules/promised-io
npm verb from cache /opt/lib/node_modules/promised-io/package.json
npm verb linkStuff [ true, '/opt/lib/node_modules', true, '/opt/lib/node_modules' ]
[cut]

My script fails on require('promised-io/promise'):

[neek@uberneek project]$ node buildscripts/stringsmerge.js 

module.js:340
    throw err;
          ^
Error: Cannot find module 'promised-io/promise'
    at Function.Module._resolveFilename (module.js:338:15)

I probably installed node and npm from source using configure --prefix=/opt. I've no idea why this has made them incapable of finding installed modules. The fix for now is to point NODE_PATH at the right directory:

export NODE_PATH=/opt/lib/node_modules

My require('promised-io/promise') now succeeds.