In fact, Ellone makes it a point to explain that she learned that you cannot alter time. All her attempts only made the the events she wished to change come true. VIII's view of time and time travel for lack of any better explanation given by the story, the Ultimania, or even Square itself points to the fact that time is linear and unchangeable in the VIII Mythos.
I've never played FFVIII before so I really have no idea what any you are talking about, but if they were doing time travel in the manner of Lost (which is possible from that description) then not being able to alter the future wouldn't really preclude Rinoa from being Ultimecia, because "whatever happened, happened" - in other words, if a time traveller's actions alter the past, it's because the time traveller's actions were supposed to alter the past. Then again that might completely contradict other aspects of FFVIII's plot; like I said, I don't know.