The Cactaur village is on Bikanel Island. But the hard thing about this sidequest to where to find it.
After "Home" gets destroyed, and you have the airship you can go back. Unfortunatly you must run all the way to where "Home" used to be. There is a woman here asking you to her baby. Ignore her for the minute and run back east ways. There are 2 places here where you can't go because "A sandstorm blocks the way" from here go south and along the map the horizontal line going east. Walk right along here and eventually you'll see a stone with a cactaur on it. examine it and it will tell you about some gateeepers which are all the different cactaurs.
NOTE: You can not find the cactaurs without examining the stone first.
When seeing a Cactaur and interacting with it, it's details will appear then it will have a screen of the cactaur and Tidus further away. The idea is to get to the Cactaur before the time runs out. But watch out there are some hazards.
When the word "needletime" appears and the Cactaur turns around stop. But din't even move anything at all or you will have failed. With the last Cactaur (Fraile) "Needletime" appears at the wrong time so just stop when he turns around.
You only get 3 goes and it you lose then you get sort of a concellation prize sphere. I don't know if you can do it with those spheres yet so if you lose 3 times, reload and start again.
Tomay: Oasis: Right near the first save point.
Rovivea: Sanubia desert (East): 3rd screen from oasis on the left, running around
Little Chava: Sanubia desert (West): West of the cactaur stone too. Examine the sign which says Rins travel agency 20% off and he will appear behind the sign.
Alec & Aloja: Sanubia desert, central: There running around to the west of the sign that says "harder fiends to the left easier ones to the right" in Al Bhed.
Valchella: Sanubia desert, south: the second save point, examine it.
Issra: Sanubia desert, west: In 1 of the sand pits on the 4th screen. If its not there then go to the previous screen and come back.
Elios: Oasis: Now run all the way back to the oasis and you'll see a Cactaur boarding the ship by the save point. Now get on the airship and go to the outside deck (where you fought Evrae) and hes here.
Fraile: He appears behind you after putting in the last sphere.
After you have caught him put his sphere into the stone and the sandstorm will disappear. Now you can get Rikku's sigil.
