infuriating isn't it?
normally if you have a non-apple email, you will get an alert every time you log in to appleid.apple.com suggesting to change your appleid to your primary email.
the error you're getting sounds like either
1) you used your preferred email associated with some other apple id at some point
2) it already *is* an apple id, ironicaly just not your main apple id.
since the email doesn't work (to verify) you have nothing to lose by
1) set a DIFFERENT email (use the verieid one) as your primary email
2) delete the prefered emaill from the 3006 apple id.
3) attempt to assign your primary email AS your apple id (don't add first as email).
it will likely error out with the same 'already used by apple id' error.
try to use the iforgot.apple.com page to discover if you have an apple id you aren't aware of using the primary email as your search criteria.
my problem was simlar yet different. there was *no way* i was going to ruin my non-email apple id by combining but since i already had used my primary email.
i suspect the non-verify issue is related to the used once somewhere else problem. makes no sense becasue you said it's your primary email, however maybe it lets you SET a primary email even though not verified.
if you can't track down the apple-id tied to your primary email, your best bet may be making a new iCloud account with a new mobileme address. (email is optional; you can have a mobileme username sans email).
-awr