After trying multiple times, and looking around for help online. One suggestion was to select Fidelity NetBenefits instead of the Fidelity Investments account when adding. (I have both a brokerage account and a 401(k) so both could have worked. However, using the Fidelity NetBenefits approach didn't work for me.
So, on to plan B... I found another suggestion that long passwords on Fidelity cause problems for Mint.com. (Lame, but not unheard of - why websites put an upper limit on password length is beyond me. What's really lame in this case is that Mint.com don't warn you that they have an upper limit on passwords they support!)
The remedy was to log in to Fidelity directly (and reset my password, since Mint.com had tried unsuccessfully enough times to lock me out - grr!). My new password is less than 13 characters long (and randomly generated using this webpage :) )
Once I had set the new, shorter, password I went back to Mint.com and added the Fidelity account. Hey presto, it works!
Now come on Mint.com and allow us to use longer passwords!