Do not use the "String" class on AVR based boards, it will most likely cause problems at some point. If you have to, use "String.c_str()" to get a "char*" string.
I understood the message, I didn't understand why the string literal worked but the String type didn't. Now I know, String is a different type to "Foo". I thought it was odd that String was capitalised.
The foo() function requires a parameter that is a pointer to a C style string (lowercase s) . This could be either a string variable, which is itself a zero terminated array of chars, or a string constant in quotes
char * message = "from the message array";
foo(message);
foo("this is a string constant");
The const tells the compiler that the foo function will not alter what the char* points to. You can pass a char* that is not const without any problems, you just cannot pass a const char* to a function that takes a char* because the function is not prohibited from altering it.