That is PC, and will be us eventually. XB1 is only to the point where PC players first got horses and nametags. They couldn't fish for them then, either. It will be a later update when we can fish or trade for them. At this point, they are only in chests in dungeons/ abandoned mineshafts.
The Meaning of Life, the Universe, and Everything.
Name tags will only spawn in dungeon chests if that terrain had not already been generated at the time of the update. If you explored the whole map before the update and you are already playing on the largest map size, you will have no name tags in your world. Otherwise, if you have unexplored terrain, search for dungeons there. If you are not playing on the largest map size, increase the map size and explore in the new territory.