Recent builds (2.4.1 and 3.0.0 tested) seem to always put in -msse into the CFLAGS. Essentally once compiled valgrind will no longer work on a CPU which isn't Pentium 3+ or Athlon XP+. Once I removed the -msse from the Makefile, valgrind works on my Athlon Thunderbird again.
Oh forgot to add this earlier, uname -a gives me: Linux NachBox 2.6.11-1-k7 #1 Mon Jun 20 21:26:23 MDT 2005 i686 GNU/Linux
The -msse is only used for some of the test suites - it is not added automatically when building valgrind itself so it shouldn't cause any problems unless you want to run the tests.
There are errors in configure script that explains such behaviour. CFLAGS variable not restored after mmx and sse checks so it contains last checked flag (-msse) after that checks. The fix is simple - add CFLAGS=$safe_CFLAGS after mmx flag check and sse flag check.
Seems that this error doesn't exist in 3.0.1 (but still in 2.4.1).
We're unlikely to release a 2.4.2. Since it's fixed in the 3.0.X line, I'm closing this bug.