Hmm, maybe check the eccentric nut on your x carriage, if it's not tight enough you'll see that kind of spurting caused by the nozzle actually being pushed upwards a little as the goo is forced down. It's believable that when you replaced the wheels the problem never really revealed itself, or maybe it turned over time because the wheel it's on isn't tight enough. (Make sure all the wheels are quite tight but not neanderthal tight.) Try to watch the carriage very closely to see if there are any very slight up and down motions. Aside from that maybe babystep up during the print and reduce flow.