You mentioned you ordered two new sim cards? Are you using those now?
For the carrier update to work well you need to use the tfdata APN. Meaning you either run the new sim card, or call Straight Talk and get someone to transfer you to the tfdata APN.
iMessage will work on wifi, so it doesn't necessarily prove that cellular data is working.
Past providers: Page Plus, AT&T, T-Mobile, Virgin, Straight Talk
Past phones: Nokia 820, Motorola Atrix HD, iPhone 4S, HTC One V, iPhone 4, Nokia Lumia 900, Nokia N9, Samsung Focus, Samsung Captivate, Nokia N900, HTC 8525, iPhone 3GS, iPhone, Nokia E61i, Siemens A56...