Gemara Eiruvin 40B: Rav Yehuda would say shehecheyanu on a new gourd.
A gourd would have the brachah of borei pri ha'adamah.
Shulchan Aruch Orach Chaim 225:6 says that it should be a fruit that is new once (or twice - Rema) a year. Otherwise, the fruit's blessing is not a criteria.
In fact, the Rema there allows a shehecheyanu blessing on a new vegetable ...