String concatenation not possible?

This isn't really rails giving you an error, it's ruby. You're trying to combine the symbols :user_firstname and :user_lastname

A symbol is a variable type, just like integer, string, or datetime (Well technically they're classes, but in this context we can think of them as variable types). They look similar to strings, and can function similarly to them, but there is no definition for the behavior of symbol concatenation. Essentially you're trying to send the method user_firstnameuser_lastname which is just as non-sensical as trying to concat two Symbols.

What you need to understand is that this parameter is looking for a method on your User object, and it won't understand the combination of two symbols. You need to define a method in your model:

def fullname
  [user_firstname, user_lastname].reject{|v| v.blank?}.join(" ")
end

This'll return your first + last name for you, and then in the parameter you should send :fullname (because that's the method it'll call on each user object in the collection):

<%= collection_select(:user, :user_id, @users, :user_id, :fullname, {:prompt => false})%>

Also, it's considered poor practice to prefix every single column with the table name. user.user_firstname just looks redundant. I prefer to drop that prefix, but I guess it's mostly up to personal preference.

The arguments for value and display attribute are method names, not expressions on a user object.

To control the format more precisely, you can use the select tag helper instead:

select("user", "user_id", @users.each {|u| [ "#{u.first_name u.last_name}", u.user_id ] })

The docs are pretty useful.