I had this problem.. Informed of a 100% jailbreak on 3.1.3 but couldnt find a Cydia icon.. Ended up then flashing to 4.1.. Still no Cydia icon..
Then went back again to 3.1.3.. This time it worked..
I didnt do anything any different but now its back to normal WITH a Cydia icon