Finally, I found the solution.
Huawei E800 couldn't be used. Instead, I used E369. That modem has 3 ports (3 ttyUSB in /dev/). If I use the 1st tty for the Internet and the second for sending/receiving SMS, then the problem disappears. Note that E800 also has 2 ttys, but it doesn't solve the problem.
I think I known how to figure out whether a modem can be used for simultaneous SMS and Internet. Need to send "AT+CMUX=0" to the modem. If it answers that the operation is not supported, then you have to try different modem.
Also I met 1 more problem on Ubuntu 13.04. If I used the ubuntu's NetworkManager to set up Internet connection, then it blocked my modem. So, the modem couldn't be used to send/recv SMS. I found the solution - didn't use NetworkManager. Instead, I set up Internet connection with wvdial. It solved the problem.