Flash Builder is a development environment: a set of tools built on top of Eclipse that make the task of developing for Flex/Air simpler. The applications you can produce are native in the sense that they are executables tailored for the environment you target the build for.
But AIR apps aren't executables in the "native" sense. To the OS, they're just data files. The AIR runtime is the executable. AIR is a virtual machine. Things like AIR are the whole reason we have the word "native" to begin with. To distinguish between virtual machines and code that is being run directly by the operating system. AIR apps are the exact opposite of native.
AIR apps are also not at all tailored for their environment (assuming you're not running any native extensions). That's one of the main strengths of AIR. You can write one set of code that will run practically anywhere. That's why virtual machines are appealing to begin with.
I don't see what the problem with running on a virtual machine would be. Most Android apps run on a virtual machine. Or isn't Dalvik a virtual machine?
However, this is true for Android and not for iOS. On Android, your application is compiled to bytecode and then run on a virtual machine. This has the advantage of allowing you app size to be smaller, since users can download the AIR runtime separately and share it among different apps.
On iOS, it is compiled to machine language. Otherwise, Apple would not allow its distribution on the app store.
Some features are tailored for a specific environment (for example, text input controls). Some features are available on some environments and not on others, and the runtime provides functions to determine whether they are available or not.
I'm not arguing that virtual machines are bad. As I said, I'm currently developing on one and I like it. What I'm saying is that the AIR download is a potential roadblock to new customers, especially on mobile platforms.
And the reason that AIR is a needed extra download is because AIR apps are not native. If they were native, there would be no need to download a virutal machine to run them.
So if Flash Builder can only make AIR apps for mobile, Adobe is precisely the opposite of correct in saying that it makes native apps. It makes virutal machine apps. And there's nothing wrong with virtual machine apps. But it is a pure oxymoron to call them native.
Well, that depends on what you call native
iOS apps are compiled to machine code. Android apps can be compiled to use a pre-installed Air runtime, or the runtime can be bundled with the app itself, without the need to download a virtual machine separately, in one seamless package to the end-user.