Gingerbread phone only queries for AAAA records?
You could report the bug to the Android developers, or vote on an existing bug, if there already is one open. This one looks a bit like the issue you are talking about.

Make sure you explain exactly what is happening, and how they can reproduce the issue.