Text messages over 160 characters still don't send. It's very inconvenient, but if I add a subject to the text message, it converts it to MMS and it sends.
I also have a ticket in with Verizon.
I have this same issue. I can not send a text over 160 characters to anyone. I found out my issue, maybe it's yours as well and this helps. I contacted Samsung and found out that on their end it shows my phone is not updated to the newest software. On my phone it states that it is. They told me my phone somehow got out of sync with their servers. To fix this you can take your phone to a best buy and get them to connect the phone to a computer that has samsung software so it can get back in sync. This service should be free of charge.
I ended up getting replacement SIM cards for both phones on Monday and so far messages over 160 characters are going through.