Alice's expected game time is (n-1)**2, as you can read in the paper "A Colorful Urn" (PDF, 82KB)
Bob's game is the famous coupon collector problem: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem.
Solving the equation for the expected value gives us 852 <= m <= 871.
We don't have an elegant solution for the more difficult version of this problem (as it was phrased before the update), which asked when Bob is expected to win, rather than when his expected value is smaller than Alice's. A simulation gives the answer as 764 <= m <= 780.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: email@example.com