Can't you just give the bullet the speed & direction the player has at the moment of shooting and then adding the bullet's own speed & direction? So if you'd shoot the same direction as you were walking the bullet's speed would be the players speed + its own speed. It should be possible to calculate the bullet's speed & angle when the player shoots in a complete different direction using sin, cos and/or tan. I can help you with that if you'd like (if you didn't try this method before and you don't know whether it works, I'm not completely sure either ;) ).
If that doesn't work out you could also consider making bullets which hit at the moment of shooting, so fast it can not be seen. You could use a thin rectangle for the bullet sprite, which will test for collisions with other objects as soon as is created (and after that it is immidiately destroyed).Edit
: I created an example of my first mentioned solution:Download
Note; Because I made the bullets so slow it might look a little weird, but this way the effect is seen best. If you have a question about it let me know ;)Jasper2013-01-24 14:19:52