With some help from lunaryorn on reddit, I guess I have been able to understand why you are observing the "wierd" behaviour.
The problem is that you are quoting the expression
'("foo" . (λ () (message "bar")))
Which is equivalent to the form
(cons "foo" '(λ () (message "bar")))
Now when emacs opens a file with extension "foo", it does something like the following
(funcall '(λ () (message "bar")))
Notice the extra quote, before (λ, this obviously is not valid function and you get the error Invalid function: ...
But then why does ("foo" . (lambda () (message "bar"))) work, this is explained by lunaryorn's observation
A “lambda list”, i.e. a list whose car is lambda, is a valid function, too
So '(lambda () (message "bar")) is a valid function, this can be verified by the following code
(functionp (lambda () "hello")) => t
(functionp (λ () "hello")) => t
(functionp '(lambda () "hello")) => t
(functionp '(λ () "hello")) => nil
So the solution would be to simply not quote the expression use the following instead
(add-to-list 'auto-mode-alist (cons "foo" (λ () (bar))))