Relationship between sampling frequency and number of coefficients
For digital filters, all frequencies (and bandwidths) are relative to the sampling frequency. So a fixed bandwidth (in Hz) becomes relatively more narrow for a higher sampling frequency. You would get the same number of coefficients (for the same performance) if the ratio $B/f_s$ were constant, where $B$ is the filter's bandwidth and $f_s$ is the sampling frequency.

I think that is basically what you already suspected, even though I think that both reasons you gave are actually equivalent.