While it looks like most of these errors on linux are caused by registration/path issues, my problem turned out to be different, so I thought I'd share my fix.

I'm mining on a brand new Ubuntu Natty Narwhal install, and after completing installation here (http://forum.bitcoin.org/index.php?topic=7514.0) with SDK 2.1 I kept getting the "FATAL kernel error: Failed to load OpenCL kernel!" error. None of the usual solutions helped (re-registering the SDK, resetting the library path, etc.).

Turns out it was the command line I was running:
./phoenix.py -u (1234)i:x@mining.eligius.st:8337 -k poclbm DEVICE=0 VECTORS BFI_INT FASTLOOP AGGRESSION=6

After dropping 'vectors' off my command line, mining works fine.