Ok, spent some time today playing around "instruments" and browsing the net learning how to fix memory leak. I think it should be fixed now, as when I re-run "instruments" the result is as shown below, there's no more leaking! Yeah!
Most of the issues are related to NSString handling. If you compare the V2.1 with V2.0 and you will easily see the differences.
Alright, spent enough time on TicTacToe, time to move on to the next project....
Source Code for TicTacToe V2.1 (Leaking Fixed)