The native code on Linux/UNIX is dependent upon NCURSES. In order to properly compile and link that code, the NCURSES development headers must be installed.
In prior releases of Debian/Ubuntu distributions, the ncurses.h header file was present in a standard gcc installation, but recent versions (e.g. Ubuntu 12.10 and later) no longer provide this by default. Make sure to install the libncurses5-dev package to get the required headers.
Install it using sudo apt-get install libncurses5-dev.