Figured out the problem, if anyone is curious:
My Makefile run by the 'make' command was missing the -lgdbm flag.
I added the following in my configure.in to check for gdbm:
AC_CHECK_LIB(gdbm,gdbm_open,,AC_MSG_ERROR("Required: gdbm database libraries"))
AC_CHECK_HEADER([gdbm.h],,AC_MSG_ERROR("Required: gdbm headers"))
Once that was included, if gdbm is installed properly, it will add that flag where needed after autoconf->configure->automake->make and also make sure the library path is setup as well.