I pulled my hair out with this too. Do you use Google Voice with your Sprint number? If so, Google somehow screws up the emojis when they handle the data. I think the other features make Voice worthwhile, so I still use it with my GS4.
My wife has a Note 3 and was using Voice and had the exact symptoms you are. We removed Voice from her Sprint account (don't just delete the app, you need to remove it from your account...see Google), and the emojis immediately began to work fine.
You might not be a Voice user, but I wanted to put this here in case someone finds this down the road.