After upgrading the tool, you need to go into the inventory to un-equip the previous version and equip the new upgraded tool. I also made this mistake, so double-check, and it will work like a breeze.