Too many coincidences? Then I'm assuming Red and Yuffie's encounter wasn't by chance?

You still haven't said that the part about Bugenhagen was just a mistake, so I'm assuming Red's been lying.

Nanaki and Barret were in on it. Barret kills Cloud while he's asleep, using his Buster Sword. He makes sure Yuffie finds him, knowing that she'll take the oppurtunity to steal his materia. Yuffie runs off with it. In the morning, Barret doesn't know what to say to Tifa, but was the one to notice and point out that Cloud's materia is missing, as a way of distracting the other party members. Red, while "going to get help," waited for Yuffie, and ended pushing her off the cliff. We know he did this because:

1. the party confirmed that no one else had been in the area.

2. 6 hours away, Red was the only one anywhere near Yuffie.

3. No weapon was used, and Nanaki could easily push her off a cliff.

We also know that Red was lying about Bugenhagen. It also doesn't make any sense that Red wouldn't try to stop Yuffie or see what was going on...
You never say whether they found the materia on Yuffie or not... Anyway, the plan was to make Yuffie to appear to be the killer.