The uncertainty principle isn't quite relevant here. Quantum physics is unitary, which means you can un-do everything by running it backward — provided you include the whole system (not just the egg) in the quantum model, including whatever physical entities are used to make measurements. The uncertainty principle implies that that certain measurements can't happen simultaneously, but it doesn't mean that the state of the physical system is "uncertain."
So even in quantum physics, your coworker is right: the egg would un-break by running the clock backward.
Despite how it looks at first, this does not actually violate the 2nd law of thermodynamics. The 2nd law isn't a statement about what is or isn't possible. It's a statement about what is overwhelmingly likely or overwhelmingly unlikely. When dealing with such huge numbers as the number of molecules in a typical egg, "overwhelmingly unlikely" might as well mean "impossible".
More explicitly, this is what the 2nd law says about un-breaking eggs: If you consider all the different possible microscopically-different states in which egg-material is scattered across the floor, practically none of them will have all of the molecules with just the right posititions and velocities to end up as an intact egg jumping back up into your hand. The key word here is practically. The very fact that you can break an egg implies that some of those states in which egg-material is scattered across the floor do have just the right molecular arrangement to end up as an intact egg jumping back up into your hand.
Why don't we ever see that happening? Because if $n$ is the number of microscopically-distinct splattered-egg states that have this property, and if $N$ is the total number of microscopically-distinct splattered-egg states including ones that don't have this property, then
n <<<<<<<<<<<<<<< N.
(I probably didn't write nearly enough "$<$"s here!) In words, the ratio $n/N$ is so insanely close to zero that no matter how hard we try, we will never be able to arrange the splattered-egg molecules in just the right way to see it un-break.
If we take quantum physics into account (as we must, because we're talking about arrangements of molecules), then the situation is even more extreme: when you break an egg, its contents become entangled with the floor, the air, and so on. In effect, the floor and air (etc) have "measured" the contents of the splattered egg by virtue of being influenced by them in a microscopically-complicated way. So not only would you have to get just the right arrangmenet of molecules in the egg material, you'd have to get just the right microscopic configuration of the whole room in order to end up with an intact egg jumping back up into your hand.
So yes, if we could run the clock backward, the egg would un-break (even in quantum physics), but that's because when we run the clock backward, we're starting with a very, very, very special molecular arrangement of splattered-egg material (and floor, and air, etc). But then why is it so easy for us to break an egg? Well, that's because any unbroken egg is itself a very, very, very special molecular arrangement of egg-material! The overwhelming majority of the choices for the positions and velocities of those molecules would not represent an intact egg at all. This, of course, begs the question of how we got such a special configuration of egg-molecules (namely an intact egg) in the first place. And if we pursue that question far enough, we run into unsolved mysteries about the quantum measurement problem and the beginning of the universe.
So I guess you could say that the fact that we never see eggs un-break has its roots in some of the deepest mysteries of the universe.
More about measurement and (ir)reversibility:
In quantum theory, the application of Born's rule doesn't represent the occurrence of measurement. Measurement is a physical process in which one part of the system (the egg in this case) influences other parts (floor, air, etc) in such a way that we have no hope of ever un-doing those effects in practice. The occurrence of such a measurement (which is a physical process) is a prerequisite for applying Born's rule (which isn't a physical process). The important point here is that we aren't required to apply Born's rule as soon as the measurement occurs. We can, but we're not required to, because — by the definition of "measurement" — the predicted (or retrodicted) distribution of possible outcomes doesn't depend on how long we wait. The fact that we can defer Born's rule indefinitely is the reason I said that the uncertainty principle isn't relevant here.
Of course, we don't (and can't) experience the whole state that results, accoring to unitary quantum theory, in the wake of a measurement. We only experience part of it (as though it had "collapsed"), and if we discard the rest, then we've sacrificed much of the information that would be needed in order to run the movie backward and un-break the egg. In this sense, egg-breaking is practically irreversible in an even stronger sense than classical physics would suggest. However, to argue that egg-breaking is truly irreversible, we would have to argue that the state really does "collapse" — and then we'd be obliged to speculate about exactly when and how that occurs. The important point here is that this would necessarily involve speculation, because we don't yet have any compelling or broadly-applicable theory of exactly how that process should work.
Thinking carefully about what quantum theory might be missing is a valuable thing to do, and I'm not trying to discourage that at all. I think about it a lot (and I still don't have any novel insights!). However, if we stick with quantum theory as-is rather than speculating about what it might be missing, then I think the appropriate answer is that we could un-break an egg as long as we didn't discard information by applying Born's rule before reversing the movie.