Had this happen to us in Calgary in freezing fog. during the preflight noticed (very slight) ice accreation on the fan blades, but didn't consider it to be too serious. However, after deice, on engine start up there was a lot of vibs. Spooled up engines again, vibs dropped and off we went.
Prior to t/o spooled up the engines again and vibs were off the scale. Throttled back and tried again, couldn't even get to the 60% target. After 3 unsuccessful attempts, taxied back to stand where I supervised a de-ice of the fan blades with hot air blowers, making sure the blades and inlet area were completely dry afterwards.
Another de-ice (airframe this time) and we were off. When we got to the runway, spooled up the engines again and vibs at the 60% target were in limits, so without spooling down we set our derate target and took off.
As we were going down the runway the vibs did creep up again and the right engine was just at the limit but not enough to abort the t/o.
When we got to our destination (OAT -35 degs C) the post flight inspection before close up showed not a trace of ice on any of the blades.
P.S. Blade de-icing with hot air blowers is an acceptable MM proceedure for severe blade ice accreation removal.