Another big clue just discovered. If I install the app (without runtime) then install the app (WITH runtime) on the same device (without removing the runtime-less version first) then then everything works.
Removing the app then installing the app WITH runtime still fails.
Found the solution (can't believe nobody else responded to this yet - well, I guess I can believe it). Anyway, the problem comes from the version of AIR being packaged. Currently I'm using Flex 4.6. This version, and as will be the case (so far) in the 4.7 release, you need to update the AIR SDK manually.
Here's what I did:
I went to my root XML file (in the src package) and changed the minimum required AIR runtime (not sure if this is a required step, but one of the two I did and now it's working - so it certainly didn't hurt). Here's how the first two lines now look:
<?xml version="1.0" encoding="utf-8" standalone="no"?>
Notice that the only thing I changed was the very end version number from 3.1 to 3.4 (the most current AIR version). Save and build.
Next is the last step. You'll need to downlaod and updated Adobe SDK and manually replace it on your local machine. The offical adobe instructions on this can be found here:
Although I found their instructions slightly confusing. Here's my revised version...
Download the Adobe AIR SDK from this link:
You'll want to unzip this and copy this to an existing folder. Here's where I was initally confused - the files within this SDK are not complete. They do not constitute the entire directory. So, you need to copy (or move) the files within the ZIP folder to the right folder. That's the second point that was confusing - exactly which folder. Go to this folder on your local drive:
C:\Program Files (x86)\Adobe\Adobe Flash Builder 4.6\sdks
This directory had two sub-folders. 4.6.0 and 3.6.0. At first I thought these referred to the AIR SDK version numbers, which didn't make sense (obviously) since the current latest version is 3.4. These are the directories for the Flash/Flex builder complies. So, I never do backwards compiling so I took both of these folders and COPIED them to an "archive" folder that I created as my backup. Then I simply copied the files from the newly downloaded AIR SDK and moved them into the 4.6.0 folder (still found at ...\sdks\4.6.0). As I mentioned before, this will overwrite some, but not all files (as it is not a complete folder replacement).
I understand this all makes much better sense when I stand back and look at it, but when you're just trying things out hoping it will fix a problem that you can't find a single google/forum/whatever response for it can be confusing.
Anyway, I hope this helps somebody out there. I'm going to list some of the things I was googling here in case somebody else is looking for the same thing.
not compatible with your device
adobe flex mobile
air runtime issues
app doesn't work with integrated runtime