One quick look at the S3 mini's spec on GSM Arena: http://www.gsmarena.com/samsung_i8190_galaxy_s_iii_mini-5033.php
It looks like the S3 min supports 3G/HSPA 900/1900/2100, which would explain why it works fine on both Vodafone and 2Degrees and not so well on Telecom since it lacks the 850 band. So you are probably safe to buy one from Telecom.
Hi, My understanding is that the S3 mini is triband GSM rather then quad band GSM. this apears confirmed by GSM Arena. Accordingly the S3 Mini will support either 850MHZ (Telecom) or 900 MHZ(2degrees/Vodafone) so will work on one or the other but not both. The support for 2100 MHZ on Telecom is extremely limited. I would say what the Dick Smith salesperson told you is correct.