What story was Jack telling when Elizabeth fell? Can someone provide the whole story?
The scene was ad-libbed by Johnny Depp. It's a reference to The Fast Show (which Depp is a fan of), where Patrick Nice often says "...and [something happened]...which was nice". In one episode, Nice explicitly says this line:
...and then they made me their chief... which was nice.
That said, the second movie: Dead Man's Chest involves Sparrow as the chief for the Pelegostos Tribe. According to the DVD audio commentary with Ted Elliott and Terry Rossio, this is the second time that he has visited them, with the first being the one that was referenced by this line.
The full story of his initial adventure with the tribe was never explained. TV Tropes would call this a noodle incident.