Ha ha.
Note to EMBOSS installers using Debian:
(1) use apt-get to install every xlib related package you can find.
(2) check that you have /usr/X11R6/lib/X11 and /usr/X11R6/include/X11
(3) check that the second of those has Xlib.h, cursorfont.h and a few others (you saw them in the EMBOSS errors)
(4) use ./configure --x-include=/usr/X11R6/include --x-libraries=/usr/X11R6/lib
make, make install, make clean.
Type "wossname". Voila.


Comments
what to install
"apt-get install libx11-dev" was sufficient for me. thanks a lot for the correct call to configure, saved me a lot of time.
still of use
Well I'm glad this ancient post (over 4 years old) was still useful!
Obviously both EMBOSS and my Debian skills have come a long way in that time. Not that I ever use the X features of EMBOSS these days.