I am having this issue also and libidn is installed as is idna.h.
However, I suspect that there is a version clash as following the suggestion to point to the correct include directory gives a heap of other errors: mainly to do with unknown types.
What version of libidn does Net::LibIDN require?