Lion comes with a version of postgres already installed and uses those binaries by default. In general you can get around this by using the full path to the homebrew postgres binaries but there may be still issues with other programs.
Found this while uninstalling / reinstalling with Homebrew. The sysadmin equivalent of “have you tried turning it off and turning it on again”. Not the last problem to debug, but one of the least visible.