"make test" not making what's tested

[kodis]

I have a simple project that builds a C program in the top level
directory, and a series of shell scripts to test this program in a
'tests' subdirectory.  If I run "./configure; make; make check",
everything works as expected, but if I run "./configure; make check"
from a just cleaned top level directory, the program to be tested
doesn't get built prior to running the tests.

I've tried adding "check" and "check-TESTS" targets that do an
explicit "make all" to Makefile.am and tests/Makefile.am, but in
addition to looking a bit dodgy, these rules don't get run.  What's
the recommended way of accomplishing this?

If it matters, I'm using automake (GNU automake) 1.10.1 and autoconf
(GNU Autoconf) 2.63 as distributed with Fedora release 10.