I think there was a bug in Xcode 4.1 where the command line tools were not installed. I just ran the 4.1.1 delta installer from the App Store and things work just fine.
Last login: Tue Sep 20 14:47:44 on ttys001
mac:~ mike$ which gcc
mac:~ mike$ ls -l /usr/bin/gcc
lrwxr-xr-x 1 root wheel 12 Sep 19 16:04 /usr/bin/gcc -> llvm-gcc-4.2
mac:~ mike$ echo $PATH
mac:~ mike$ mkdir /tmp/test
mac:~ mike$ cat > /tmp/test/hello.c << EOF
/* Hello World program */
mac:~ mike$ cd /tmp/test
mac:test mike$ gcc hello.c -o hello
mac:test mike$ ./hello
Hello Worldmac:test mike$
This should work out of the box with the latest Xcode. Have you made sure you are using the latest gcc / Xcode and not having previous path or binaries installed?