Just to add my four bob to this thread. We recently had the case of a client wanting to use the .co version of his business name as opposed to his .com.au. The .com belonging to a competitor. His re designed website was launched under the .co domain and the feedback from his clients and colleagues who he emailed using the .co email address was that the .co looked suspicious and spammy, as an email address firstly, and the web address was seen as something that did not resonate well with the local and international market.
I think the .co domain will take some time to be accepted for regional search engines such as Australia until the domain name becomes more readily accepted into mainstream website development and more commonplace.