from what i have heard, 3 service has certain features which require certain mobiles, which are available with 3.
eg. of these features include 3G, which require a 3G compatible mobile phone. when you purchase a 3 connection, and get a mobile with it, it would most probably be compatible.
on the other hand, vodafone may not be using 3G services, hence does not distribute 3G phones.. ( i don't have much idea about the services available in australia and hence this is just an assumption)
The best way to see whether your phone is compatible is just to make sure whether 3 also gives that particular model with its services, or any other similar model.
What phone is it anyway?