Hi Andrew,
Thanks a lot for your reply. That makes sense to me...
As it happens, I just found out what was causing the problem: I have a MacPorts version of bash installed, and its path is not a symlink... yet for some reason Terminal has a problem if you specify a custom shell and the path to it is not a symlink. It's not just Alfred it has problems with, but other utilities too. Anyway, the fix was easy enough, and is working well now.