I had similar problems with Ubuntu 12.10 (quantal), but it worked with:

sudo apt-get install libminiupnpc-dev libminiupnpc8


which installed all the necessary header/library files.
The versions for narwhal will probably be different -
You can:
apt-cache search libminiupnpc

to find them.