We have three Kindle Fire HDs in the house and none of them can see each other when searching for game/worlds. However, recently we were with a group of various platforms (iPhone, Samsung pad, iPad) playing together. I was hosting a game on my Kindle Fire HD, one of the iPhone's joined the game. The minute he joined my game, my daughter's Kindle Fire HD which previously could not find/see the world was able to discover AND join successfully.
Summary: KFHD to KFHD do not see each other. Add another platform (such as iPhone/iPad/Tablet) to the KFHD hosted world and then other KFHDs can see/join.
Possibly a broadcasting challenge with KFHD? Once another platform joins, it broadcasts the signal as well, allowing other KFHDs to see?
Did we just get a huge update and absolutely no fix for the Kindle Fire HDs?