If you install
http://perian.org/ quicktime will be able to play mkv files including the ac3 audio.
You can use Quicktime to save the file as a mov which should then play on the AppleTV. Personally I use VisualHub, it's much faster and allows you to queue up a batch to process. It will depend on your system, but my machine will recode a TV show in approx. 30mins.
The Visualhub method will loose the surround sound. AC3 and DTS are not supported by the mp4 container so it will be converted to stereo. You should be able to keep the AC3 or DTS in a mov, but I've not tried this so I don't know whether the AppleTV will play the file.
As the new firmware will allow for HD movies with surround sound (according to the MacWorld keynote) there might be a fix for this then. We'll have to wait for someone to rent a movie and see what the container and codecs used are. Hopefully we'll be able to use 5.1 AAC and the AppleTV will convert that to AC3 out of the optical output for my surround amp as AC3 and DTS take up a lot of space.