The main cause of your problem is the usage of the notifyAll() method. If there are more than one thread waiting, then you wake them all up. So if you put one object in the queue, the first one the wake up will take it while the others will get the error.
However, even if you change it to notify(), this can still happen -- although less likely. There is a chance that the one thread can get the notification, but before it reacquires the lock and wakes up. Another thread checks for empty, finds it not, and processes the data.
Changing it from an if to a while is the right solution. You probably don't need the notifyAll -- a notify should work.