I was trying to avoid doing double conversion, as it quickly gets confusing, and I'd have to update prices each time USD/AUD changes, as well as each time USD/BTC changes. Either that or I'd have to build in a buffer amount, which I'm trying to avoid.
Maybe I'll just have to start an AUD exchange!
Keep it simple for now. Stick to your guns here with Australian dollars as that is something you can personally work with and force conversion rates through bitcoins (there are now several people who are exchanging bitcoins for U.S. dollars and other currencies). If you want to get more complicated over time, that is something separate you can work with after you have something basic going. It may be easier to simply stay simple and let others get involved with more complex transactions. If you do engage with foreign currencies, make sure you charge a healthy premium for the service.
Since you will be dealing with real banks and real currencies, get some advise from some professionals whose job it is to deal with this stuff. Going to a local bank and talking with a bank manager might be a good idea, or at least somebody other than just a teller. Don't worry about giving away everything, as this is going to be speculative on your part and it will be something the bank won't get involved with right away (given the nature of bitcoins at the moment). Hopefully what you are offering is the technical expertise and the willingness to invest your own capital into this project.... two things that can really smooth the way. It would also be in the interest of the bank to get involved with you as it has the very real potential of increasing their business substantially.
Most of the questions you are asking can be answered by that banker including the legal issues and even many of the pricing and marketing issues. They may even recommend some ideas you haven't thought about. Make sure that you set up an appointment ahead of time, or engage in a very brief (one minute or so) conversation hinting that it may take you awhile to explain the full concept and would like to explain the details at a later time. Seriously, this is a money making idea and something unique enough that it will get some heads to turn if you offer it. Talking about the global nature of Bitcoins and that there are people with U.S. Dollars and Euros willing to get in on this may really get that banker thinking about some possibilities.
The largest problem you will be facing is in terms of what you are going to do with all of the bitcoins you may be receiving. Finding somebody willing to trade you AUDs for bitcoins would be the final circle that could help you out, or simply setting up an exchange like you suggested where you could take payment (with fees put into the schedule) to ship bitcoins to somebody.
Also, plan ahead for now in terms of what kind of capital you are willing to invest into this project, both in terms of computer systems for the website/interface to your project and for how much money you want to invest into the card program itself. Only you can make that determination, but also plan for the possibility that it may take much more cash than you originally anticipated. Make a clear business plan (even if this is just going to be a hobby) and above all at least plan to be profitable (or at least not losing money personally) in as short of a time frame as possible. It doesn't have to cost a whole lot to get this going, and one really nice thing about this kind of business is that the capital requirements also don't have to be earned all at once.