At least here on Fedora 17, the "TF2 just crashes at start" issue is caused by SELinux killing the process due to the app making its heap memory executable.
How can you fix this? As root (e.g. prepend sudo) do setsebool -P allow_execheap on
Please do note that this is actually rather bad and you shouldn't leave the bool set to enabled for longer than you're actually playing the game (can be disabled using "setsebool -P allow_execheap off")