JPEG support needs to be compiled into GD.  If the GD library you link into PHP doesn't have support for JPEG, then linking the JPEG library into PHP has no effect.

Your fix would be editing the GD Makefile;
CFLAGS=-DHAVE_JPEG

--Mathieu

I did CFLAGS=-DHAVE_JPEG and when I do a Make I get the following.

gcc -I. -I/usr/local/libpng-1.0.8 -I/usr/include/X11 -I/usr/X11R6/include/X11 -I/usr/local/include -I/usr/X11R6/include/ -I/usr/local/jpeg/work/jpeg-6b gdtest.o -o gdtest      -L. -L/usr/local/libpng-1.0.8 -L/usr/lib/X11 -L/usr/X11R6/lib -L/usr/local/jpeg -L/usr/X11R6/include/ -lm -lgd -lpng -lz
./libgd.a(gd_jpeg.o): In function `fatal_jpeg_error':
gd_jpeg.o(.text+0x45): undefined reference to `jpeg_destroy'
./libgd.a(gd_jpeg.o): In function `gdImageJpegCtx':
gd_jpeg.o(.text+0x191): undefined reference to `jpeg_std_error'
gd_jpeg.o(.text+0x1fb): undefined reference to `jpeg_CreateCompress'
gd_jpeg.o(.text+0x236): undefined reference to `jpeg_set_defaults'
gd_jpeg.o(.text+0x251): undefined reference to `jpeg_set_quality'
gd_jpeg.o(.text+0x26c): undefined reference to `jpeg_simple_progression'
gd_jpeg.o(.text+0x2c8): undefined reference to `jpeg_destroy_compress'
gd_jpeg.o(.text+0x2ea): undefined reference to `jpeg_start_compress'
gd_jpeg.o(.text+0x392): undefined reference to `jpeg_write_marker'
gd_jpeg.o(.text+0x491): undefined reference to `jpeg_write_scanlines'
gd_jpeg.o(.text+0x4d8): undefined reference to `jpeg_finish_compress'
gd_jpeg.o(.text+0x4e7): undefined reference to `jpeg_destroy_compress'
./libgd.a(gd_jpeg.o): In function `gdImageCreateFromJpegCtx':
gd_jpeg.o(.text+0x5a3): undefined reference to `jpeg_std_error'
gd_jpeg.o(.text+0x627): undefined reference to `jpeg_CreateDecompress'
gd_jpeg.o(.text+0x64b): undefined reference to `jpeg_read_header'
gd_jpeg.o(.text+0x73a): undefined reference to `jpeg_start_decompress'
gd_jpeg.o(.text+0x8dd): undefined reference to `jpeg_read_scanlines'
gd_jpeg.o(.text+0x980): undefined reference to `jpeg_finish_decompress'
gd_jpeg.o(.text+0x9a8): undefined reference to `jpeg_destroy_decompress'
gd_jpeg.o(.text+0x9d0): undefined reference to `jpeg_destroy_decompress'
./libgd.a(gd_jpeg.o): In function `jpeg_gdIOCtx_src':
gd_jpeg.o(.text+0xc4b): undefined reference to `jpeg_resync_to_restart'
*** Error code 1

Stop.
"

I even tried doing a Package add. It added the package without any complains. But then it is hard to compile a package into PHP.

I did CFLAGS=-DHAVE_JPEG and when I do a Make I get the following.

gcc -I. -I/usr/local/libpng-1.0.8 -I/usr/include/X11 -I/usr/X11R6/include/X11 -I/usr/local/include -I/usr/X11R6/include/ -I/usr/local/jpeg/work/jpeg-6b gdtest.o -o gdtest      -L. -L/usr/local/libpng-1.0.8 -L/usr/lib/X11 -L/usr/X11R6/lib -L/usr/local/jpeg -L/usr/X11R6/include/ -lm -lgd -lpng -lz
./libgd.a(gd_jpeg.o): In function `fatal_jpeg_error':
gd_jpeg.o(.text+0x45): undefined reference to `jpeg_destroy'
./libgd.a(gd_jpeg.o): In function `gdImageJpegCtx':
gd_jpeg.o(.text+0x191): undefined reference to `jpeg_std_error'
gd_jpeg.o(.text+0x1fb): undefined reference to `jpeg_CreateCompress'
gd_jpeg.o(.text+0x236): undefined reference to `jpeg_set_defaults'
gd_jpeg.o(.text+0x251): undefined reference to `jpeg_set_quality'
gd_jpeg.o(.text+0x26c): undefined reference to `jpeg_simple_progression'
gd_jpeg.o(.text+0x2c8): undefined reference to `jpeg_destroy_compress'
gd_jpeg.o(.text+0x2ea): undefined reference to `jpeg_start_compress'
gd_jpeg.o(.text+0x392): undefined reference to `jpeg_write_marker'
gd_jpeg.o(.text+0x491): undefined reference to `jpeg_write_scanlines'
gd_jpeg.o(.text+0x4d8): undefined reference to `jpeg_finish_compress'
gd_jpeg.o(.text+0x4e7): undefined reference to `jpeg_destroy_compress'
./libgd.a(gd_jpeg.o): In function `gdImageCreateFromJpegCtx':
gd_jpeg.o(.text+0x5a3): undefined reference to `jpeg_std_error'
gd_jpeg.o(.text+0x627): undefined reference to `jpeg_CreateDecompress'
gd_jpeg.o(.text+0x64b): undefined reference to `jpeg_read_header'
gd_jpeg.o(.text+0x73a): undefined reference to `jpeg_start_decompress'
gd_jpeg.o(.text+0x8dd): undefined reference to `jpeg_read_scanlines'
gd_jpeg.o(.text+0x980): undefined reference to `jpeg_finish_decompress'
gd_jpeg.o(.text+0x9a8): undefined reference to `jpeg_destroy_decompress'
gd_jpeg.o(.text+0x9d0): undefined reference to `jpeg_destroy_decompress'
./libgd.a(gd_jpeg.o): In function `jpeg_gdIOCtx_src':
gd_jpeg.o(.text+0xc4b): undefined reference to `jpeg_resync_to_restart'
*** Error code 1

Stop.
"

I even tried doing a Package add. It added the package without any complains. But then it is hard to compile a package into PHP.

The answer to your problem is in the gd Makefile.
There are more lines to edit than just the CFLAGS line.

You need to add -ljpeg to the LIBS line.
You need to add the path to jpeg-6b
to the INCLUDEDIRS line, thus: 

INCLUDEDIRS=-I. -I/yourpathto/jpeg-6b/

All this information is in the Makefile and gd docs.
RTFM please.

In any event, this is not a php problem.