I have heard this "fact" many times. Another version states that this is especially true in the summer.
I was on a trip to Italy only last month and visited Venice as part of it. I spent three days there, took vaporettos (ferries) and walked most of the time. The water ways and canals do host a wide variety of algae and water-weeds and it is indeed true that you occasionally get a whiff of "algae-odor" when the wind's right and you happen to be on the side of some particular water-ways or canals.
It smelt different to me but not bad. However, stating this as a reason for not going to Venice is as lame as saying one should not go to Chicago because of high crime rate and mugging incidentsalmost laughable.