After some googling and trial-and-error, i finally found the solution to this one. I suspect that other people may also come across this problem, so i'm posting it here.
I use Hadoop-1.0.3 (the tar.gz package, not the .deb or .rpm)
In my program's Makefile i was initially using the libraries in $(HADOOP_INSTALL)/c++/Linux-amd64-64/
I actually had to recompile these from source -with a couple of tweaks before- and include the new ones instead.
So, first of all, since i'm running Slackware64 14.0, I enabled the multilib support.
1. Export a variable LIB=-lcrypto. (I actually put it in /etc/profile, so that i don't have to export it every time).
2. in $(HADOOP_INSTALL)/src/c++/pipes/impl/HadoopPipes.cc add
3. In $(HADOOP_INSTALL)/src/contrib/gridmix/src/java/org/apache/hadoop/mapred/gridmix/Gridmix.java, replace the two(2) lines described here
4. In $(HADOOP_INSTALL)/src/c++/utils run
5. In $(HADOOP_INSTALL)/src/c++/pipes run
6. In the new Makefile, use
-L$(HADOOP_INSTALL)/src/c++/install/lib -lhadooputils -lhadooppipes -lcrypto -lssl -lpthread
That was it. Programs runs fine now.