REXMLは内部でiconvをバカ使いしてるので、日本で使われてるShift_JIS名義のXMLが苦手だったはず

headline_url = "http://yp.ladio.livedoor.jp/stats/list.xml"
xml = open(headline_url).read
xml = xml.sub!(/encoding="shift-jis"/){'encoding="CP932"'}
aa = REXML::Document.new(xml).root

でどうだ