Can you upload a copy of the source with just the two objects and events for shooting? It sounds like the hotspot of the bullet hasn't been centered. Sprites start at 128x128 size, so after shrinking to 16x16 it's possible the hotspot is still outside the object.
Also, you could be spawning the bullet at the hotspot of the main character as well, try spawning the bullet at image point 1 if you're not spawning it at the image point name (as image point 0 is the hotspot).
I've not seen hotspots and image points mentioned much on the forums, so here's a quick write up on how they work: Hotspots are the red dots and can only have one per object as that is where the X and Y for the object are calculated from, when positioning objects they are treated as image point 0.
Image points are manually placed and added to sprites, and they are numbered from 1 and up, or can be named.
There is also issues at times where placing an image point will move your hotspot or vice versa, so it's worth checking the hotspot and image points are all in correct places after working with them.