What are some good ways of marketing a Bitcoin related service to Bitcoin users?
The folks at bitcoin.it run a moderated listing, https://en.bitcoin.it/wiki/Trade, which you can list at.  Another way is to work directly on reddit (r/bitcoin) and http://www.bitcointalk.org/.