I know this may be a bit after the fact for this thread, but my two-bits worth are: in 1999 we did LAX-TPE-DPS and back for pretty cheap (for non-non-revvers which we were back then: about $1000) on BR (Eva Air), who back then had a very comfy super-coach class almost like Business, for $100 more each way.
Now we're non-revving parents with NW, and are looking into Bali again for next Winter. Found that Korean Airlines have JFK-Seoul-DPS and NW has ZED agreement with them. We're gonna try to do either that (Jan 2007) or LAX-TPE-DPS on BR who also have ZED accord w. NW.

Hope you will have or had a great Bali time. Ubud in the center is highly recommended!