Question:
How can I enable users to select "All" as the value of a multivalue query parameter?

Answer:
Since multivalue parameters cannot be null, you cannot use the approach previously described here.  Fortunately, a simple modification of that approach to use a non-null "ALL" token is all that is required.

Step 1:  Start with a report that already has a parameterized query and Valid Values queries.

Step 2:  Edit your base query to account for "All".
Whever you have something like this:
 ... AND Field IN (@Parameter) ...
Replace it with this:
 ... AND (Field IN (@Parameter) OR 'ALL' IN (@Parameter)) ...

Step 3:  Edit your Valid Values queries to insert an explicit "All" and separate ids from labels
For example, for this original query:
     SELECT name FROM productcategory
Change it to this:
     SELECT 'ALL' as ID, 'All' as Label
     UNION ALL
     SELECT name as ID, name as Label FROM productcategory

Step 4:  Update the report parameters
Set the default value of each parameter to ALL
Change the valid values settings to account for the new field names (if needed).

Step 5 (Optional):  Update Valid Values queries to account for "All".
If you have hierarchical parameters, in some cases, you may want the dependent parameters to be independently selectable when the parent parameter's value is "All".  In this case, repeat step 2 for each of your Valid Values queries.  Note: Don't do this if you have extremely large numbers of possible values, as performance will suffer and your users wouldn't be able to nagivate an excessively long list anyhow.

A full working sample of multivalue "All" parameters is attached.