I saw the same thing this week, and it turned out to be because there were values in my multi-valued parameter's "default list" that were sometimes NOT in the data selection -- in my case, the default list's values were invalid for some dates I might select.
Here's what caught me: SSRS allows invalid values in the default list during development previews, but does not allow them in production.
In my example, the report was being developed in Report Builder. When I did a "Run" (a preview) of the report in Report Builder, the list parameter's checkboxes were selected for the default list's values, as designed. But when I saved the report, and ran it as a user would -- running the report from the Reporting Services browser page -- then no values were selected -- no defaults.
Then, to fix this, I took all selection criteria up to that point, and applied them to the default list -- making sure the "Default Values" only included values within the "Available Values" -- then the default values were selected, BOTH in Report Builder development, and in SSRS production.
EXAMPLE: assume my selection query for "Available Values" was:
SELECT Type
FROM MyTable
WHERE Date <= @BEG_DATE
AND Date >= @END_DATE
And assume that, using 1/1/2013 and 12/31/2013 as dates, that the above returns 'A','B','C','X','Y','Z' as the list of values, for the user to select from (presented as checkboxes).
Now, assume that my selection query for "Default Values" was:
SELECT Type
FROM MyTable
WHERE Type IN ('A','B','G','H')
The problem in this example would be that, for dates 1/1/2013 and 12/31/2013, the default values "G" and "H" are not valid values.
The fix in this example would be to add to the 'WHERE' clause, in the "Default Values" query. It becomes:
SELECT Type
FROM MyTable
WHERE Type IN ('A','B','G','H')
AND Date <= @BEG_DATE
AND Date >= @END_DATE
Now, when this default values query is run for dates 1/1/2013 and 12/31/2013, the "G" and "H" drop out of the default values, and leaving only "A" and "B" as default values. "A" and "B" can both be selected, because they are also both in the Available Values for the parameter. So, defaulting the multivalued parameter now works, BOTH in development, and after saving the report (after deploying, after publishing) and running it from a browser.