This is a generic issue with high bitrate 720p files and AppleTV, yes.
AppleTV is only powerful enough to do low bitrate 720p in standard setup. To be able to do high bitrate 720p and 1080p you need the Broadcom CrystalHD card. Please keep in mind, the CrystalHD card will replace the wireless card in AppleTV, but since you cannot stream 1080p reliable over wireless anyway, I do not see it as a loss.
The CrystalHD card comes in 2 versions. The BCM70015 does MPEG-4 ASP (XviD/DivX) where the BCM70012 does not. However both XviD and DivX are easly handled by the CPU software decode under the AppleTV. The BCM70015 is 1/2 the length of the BCM70012 and requires less power.
Support for the BCM70015 is rolling in to OSX/Linux driver/lib, see the commit log for crystalhd-for-osx at googlecode. Of course the BCM70015 will be supported by XBMC. The lib API is identical.
The ebay BCM70012 cards were old layout and ebay sellers appear to have exhausted their source for the older card. It was never clear where they obtained them as they were never sold unbundled. New layout BCM70012 cards are available from http://www.logicsupply.com (USA only).
The BCM70015 should appear unbundled in Q2-Q3 of 2010. I think they are already being sold bundled with various netbooks.
If you intend to order, LogicSupply is offering a $10 discount for XBMC users, use “XBMC10” as the discount code when purchasing.