I was very exited to install appium but one major issue I encountered is that you can't npm-install it using sudo. Well that's really annoying because I'm installing it on a VM that has a shared folder, and I have to use sudo... damn... So I tired several solutions, and found that the best thing to do, is install nodejs and npm allover again using Homebrew.
I thought it's a good place to share the process I went through: Note that I'm running Ubuntu 13.04 64bit Using VirtualBox. This solution worked for me, but I hope that will help someone, someday. Enjoy!
Uninstall node and npm: