Two things to think about. Is physics (i.e., the description we understand of the universe) deterministic, and then is is time symmetric? The answer to the first is yes, and the second is no. This answers treats both because tHey are Intrinsically related to the question of whether the universe would evolve back to the same if we reversed time. Clearly, if it was time symmetric but not deterministic, nothing would ever go back to the same.
This covers it all, though some of it summarily. But I try to describe and answer this using physics, and identify what may not be well known or accepted physics. There is lots of good physics to cover.
The basic answer seems to be that it is deterministic (in a strange but well understood way even in quantum physics), but not time symmetric (both microscopically and macroscopically).
At its basics the universe is deterministic, though in practice that's a different question. The question of whether the universe is deterministic was asked and had a number of answers in 2013, see Is the universe fundamentally deterministic?
The answer that emerges there, and the answer backed by known physics, is that basically it is deterministic, if we believe the currently best known physics, the Standard Model and General Relativity (GR). That is at a microscopic level plus relativity. It ignores the possibility that unknown physics such as Quantum Gravity would say otherwise, since we don't have a theory for Quantum Gravity yet. Clearly it also ignores what may be found at much higher energies than we have been able to measure things at, in what would be called Beyond the Standard Model'. Also, GR may allow closed timelike curves (CTC), which would also imply a breakdown of causality (which requires nothing faster than light, in the physics we know). For causality reasons most physicists think CRCs are not possible, except in regions separated from us by event horizons such as inside black holes so that we would not be affected. There are some strange GR solutions that allow CRCs, but they seem to not be physically possible. That does remain a controversy. This is not philosophy, it is pure physics, and with that possible exception the universe is causal and deterministic (I know, an exception is an exception, we just don't know about those yet)
There is another factor to account for, and two items to explain. First, account for entropy and thermodynamics, then about wave function collapse and the measurement problem. Both of those are still a bit controversial, but there is some semi-consensus that is emerging. That is the next two paragraphs. The third is simply a misunderstanding by laymen that quantum physics is not classically deterministic i.e., the uncertainty principle. That also is explainable and physicists agree that quantum physics is deterministic, eg, the Schrodinger, Dirac, and all other quantum physics (in quantum mechanics and in quantum field theories) all predict the quantum physics we see; the simplest way to see it's to understand that in QM the wave function is perfectly predictable. @Bush explains below that it is not if position or momentum is predictable but whether the wavefucntion (or other quantum equivalents) are deterministic. They are. In overall quantum physics that comes from the fact that all the evolution equations we know for the standard model are unitary. That's the technical term for information is conserved. Black Hole physics seems to contradict it with the horizon, but even Hawking has agreed that information is conserved, and people are trying to solve the 'paradox'. See Hawking's latest described simply, and the reference to his June Phys Rev Letters at http://phys.org/news/2016-06-hawking-team-soft-hair-theory.html
For entropy and thermodynamics it's simpler. Those are simply statistical macroscopic observation we have to make when detailing the evolution of all the quantum fields everywhere in the universe can not be computed. It's a practical and smart way to deal with the largeness, but it is our lack of knowledge we compute in entropy, not the universe.
As for wave function collapse not being unitary, or breaking the quantum physics laws, the well understood (not by laymen) answer is that if you include the evolution of the measuring apparatus, it is unitary and there is no collapse, just interactions that make the original wave function decohere. It appears to collapse if we caused it, but it simply interacted with us unitarily.
So the symmetry going back in time can ignore all of that, and and simply be answered by whether quantum physics is time symmetric, plus the additional issue of initial conditions in the large. On time symmetry, it is known that physics is not. The weak force breaks time symmetry, and CP symmetry. The CP symmetry breaking has been known, it is why there are only left handed neutrinos. (CP symmetry may also be broken, very very weakly, by the strong force, there are physical observations that hint at it, but it is not clear, and it has never been measured to be so). CPT symmetry (T is time symmetry) has never been found to be broken, so when CP is broken so is T. It is complicated but it seems to be so, and it is hoped that the CP breaking will explain why there are more particles than antiparticles in the universe, still an unsolved issue. See on T symmetry at https://en.m.wikipedia.org/wiki/T-symmetry and a lot of references there and elsewhere. The weak force is not time symmetric.
The final argument is the question of why are we evolving forward? Macroscopically it is thought now that it has to do with the initial conditions of the universe and entropy. That it was created in a low entropy state, and the evolution microscopically to a state of higher and higher entropy is the reason for the direction of the time arrow. Well, macroscopically it seems reasonable, but is that inherent in the universe or our perception? Physically there is still arguments going back and forth and it is sometimes described as philosophy. The time arrow exists in microscopic physics in the weak force, but is is totally unclear how that manifests itself in macroscopic physics and entropy.
But taking that into account then the answer is that if you run the universe backwards from where it is right now somerhing would be different. Microscopically, the weak force time asymmetry would change some of the evolution, and macroscopically the initial conditions would make it go towards a higher entropy rather to back to a small entropy.
Lots of physics in that (which has physical, real effects) but some unknowns people call philosophy, and which may or may not have physical effects.
Best Answer
The reasoning in the question is correct. If you have a box with gas particles placed in half of a box but otherwise uniformly random and with random velocities then it is overwhelmingly likely that it entropy will increase with time, but if reverse the velocities, you will still have randomly distributed velocities and the same argument will apply. By time symmetry reversing the velocities and going forward in time is equivalent to going backward in time. So system prepared as described above would almost certainly be in local entropy minimum wrt to time.
If the whole universe only consisted of some water with unevenly distributed dye in it, and we knew nothing about its origin, then inferring that the dye was more evenly distributed in the past would be rational. The water and dye being in a beaker near a teacher in a far from equilibrium universe makes other explanations much more likely though. However, your line of reasoning has some bite at the cosmological level. This is the Boltzmann Brain Problem. It is still not satisfactorily resolved, as you can see on ArXiv.
The second law of thermodynamics works (and is a law) because the universe is far from equilibrium (ie low entropy) and is believed to have started much farther from equilibrium that than it is now. Of course a big part of the reason for believing that is the second law. ;)
Here is a more detailed explanation from my answer to Where does deleted information go?:
The apparent conflict between macroscopic irreversibility and microscopic reversibilty is known as Loschmidt's paradox, though it is not actually a paradox.
In my understanding sensitivity to initial conditions, the butterfly effect, reconciles macroscopic irreversibility with microscopic reversibility. Suppose time reverses while you are scrambling an egg. The egg should then just unscramble like in a film running backwards. However, the slightest perturbation, say by hitting a single molecule with a photon, will start a chain reaction as that molecule will collide with different molecules than it otherwise would have. Those will in turn have different interactions then they otherwise would have and so on. The trajectory of the perturbed system will diverge exponentially from the original time reversed trajectory. At the macroscopic level the unscrambing will initially continue, but a region of rescrambling will start to grow from where the photon struck and swallow the whole system leaving a completely scrambled egg.
This shows that time reversed states of non-equilibrium systems are statistically very special, their trajectories are extremely unstable and impossible to prepare in practice. The slightest perturbation of a time reversed non-equilibrium system causes the second law of thermodynamics to kick back in.
The above thought experiment also illustrates the Boltzmann brain paradox in that it makes it seem that a partially scrambled egg is more likely to arise form the spontaneous unscrambling of a completely scrambled egg than by breaking an intact one, since if trajectories leading to an intact egg in the future are extremely unstable, then by reversibility, so must trajectories originating from one in the past. Therefore the vast majority of possible past histories leading to a partially scrambled state must do so via spontaneous unscrambling. This problem is not yet satisfactorily resolved, particularly its cosmological implications, as can be seen by searching Arxiv and Google Scholar.
Nothing in this depends on any non classical effects.