under $500 INCLUDING taxes?
That would mean you're after a sub ¥40,000 ticket (taxes are rarely included on published fares)
http://www.iace.co.jp/english/tokyo/
Has ¥53,000 tickets from Tokyo to Jakarta for your dates - the taxes will make this more expensive - but should be under $700 for a ticket.
There's a list of consolidators for you to try here:
http://www.flyertalk.com/forum/showthread.php?t=323865
no1-travel may have cheaper tickets to Bali about a month before your date - they currently have tickets for ¥44,000 (tax excluded) for travel from Tokyo to Bali in the next few weeks. They
do have ¥33,000 tickets to Singapore available now.
Anyway, you have a list now - I'll let you do the leg work.