Maddy's comment about the beacon being placed in the probe so that "they could find it however many millions of years later" seems to indicate that the probe's designers expected the probe and beacon to remain intact and functioning for millions of years so that it could be located in the 22nd century (as opposed to the beacon just sending signals back through the Time Portal). This would require that the probe and beacon be made of some amazingly durable material, given that over millions of years weathering and geological processes can grind down enormous rocks and other normal materials (not to mention the possibility of disasters like being enveloped in volcanic lava or being at the center of a large meteor impact). And presumably there'd be no way to rule out the possibility that the colonists, or their future descendants, would at some point decide to take apart the probe using the same type of technology that was used to create it. So, if the notion that Terra Nova lay in a separate time-stream was based solely on the fact that the probe and beacon hadn't survived 85 million years to be found somewhere in the 22nd century, the conclusion appears to be somewhat shaky.
Many time travel stories attempt to avoid paradoxes by imagining that the act of traveling back in time creates a new parallel time-stream, which branches from the original time-stream at the moment the traveler arrived in the past (see "3. Alternate timelines" in the Rules of time travel section of wikipedia's Time travel article). So, it could be that Terra Nova is located in a parallel time-stream whose history was the same as the original one up until the moment the Time Portal first appeared 85 million years in the past, but which branches off after that point, with the Time Portal providing a stable bridge between the two time-streams (the branching point might also have occurred when an earlier rift opened up between the human era and world of 85 million years ago, as suggested by the scene at the end of "Occupation-Resistance" with the old-looking ship's figurehead). On the other hand, Terra Nova could be located in a completely parallel universe which was never identical to our own universe at any point in its past, with the resemblance to our own past being coincidental. Possible evidence for the "branching time-stream" theory is that this summary of the original pilot script says "For you science nerds out there already wondering how they get around the time travel paradox in Terra Nova, there's a bit of throwaway dialogue said by one of the main characters. By traveling to the past humans are in fact creating an alternate Earth, one that branches off of our own timeline." An additional piece of possible evidence is that people associated with creating the show have made statements suggesting that they want to keep things within the bounds of what could have plausibly been true about the real past (which wouldn't seem necessary if it was a parallel Earth with only coincidental similarities to our own past). For example, this article gives some comments by science advisor Jack Horner:
Horner said he's willing to give the writers and artists wide latitude when it comes to dreaming up dinosaurs. "If we know something for sure, then we'll keep it within the bounds of science," but if there are blank spaces in the scientific picture, a little (or a lot of) imagination is allowed.
Similarly in this interview, executive producer Rene Echevarria points to the fact that the dinosaur fossils we have found are only a small fraction that actually existed, to justify the various made up dinosaur types like Acceraptor and Nykoraptor on the show. When asked, "You guys are using some real dinos, and there are some made up dinos. I know you were consulting with paleontologist Jack Horner. Can you talk a bit about them? These are dinosaurs that could have existed, right?", Echeverria responds "Could have existed? Absolutely, yeah. Jack has represented to us that probably 10% of the species that existed at the time have been accounted for in the fossil record. So while he vets every design, and can be pretty strict about certain things...behavior, how they move and things like that, there is a wide latitude for the kinds of creatures that really existed." Finally, in this interview with Executive Producer Brannon Braga, the interviewer asks "How are you going to deal with the extinction event that happens to kill off the dinosaurs?" and Braga responds "Well, that's a problem they're going to have [in the future]. There's an asteroid coming." This response again seems to suggest a branching timeline where the same asteroids are present in space on the same courses, rather than a parallel world with only coincidental resemblances to our own (in the latter case there wouldn't seem to be any particular reason to expect an asteroid impact just as in our own history).