So what's your real problem? You can't find each other in underground? Or you don't know how to get Spiritomb to appear?
FYI, Spiritomb appears after you've talked to 32 "different" people underground. You can exit and re-enter and talk to your brother 32 times to achieve the same effect. You don't need to have beaten anybody in particular or have obtained any badges, you just need to put the odd keystone in the well, talk to 32 people underground, and look at the well to battle Spiritomb.
To be together in underground: did you guys go underground in similar locations? (did you guys go underground in the same city or same route, etc) Other than Wi-Fi issues (which is rare) the only reason you guys aren't showing up on each other's screen is because you're not actually next to each other; physically sitting each other in real life doesn't do anything but increase Wi-Fi lag. You guys still need to go underground near each other in the game (just do it near the well)