I have read that there is a bug on ICS 4.0.0 - 4.0.2 that will not allow you to format NDEF.
To get around this you have to order your tags already formatted or install a ROM that is based on 4.0.3 or above (bug was fixed in 4.0.3)
Tagstand.com will Pre-format tags, it is a few cents extra.
You can try buying tags from www.buynfctags.com, they sell tags with NTAG Chips and these are pre-formatted with NDEF. They do sell other tags with the UL, ULC, or 1K chips, and you get the company to NDEF format them for you.
Tagstand sent me a ton more tags (I think I lost some LOL) and they sent me a box of cookies too!
Tags are working great.
They refunded my money and sent me stuff which I offered to pay for. Excellent CS...happy with them after the frustration.
I do see a difference too since the new tags came. The first batch you had to be exactly on top of it to get it to read the tag correctly. The new ones seem to have a stronger connection.