sounds to me also like you have not hit the brickwork yet and are jsut in plaster.
Sometimes if your unlucky/your drills not much cop/or your mortar bits are not much good, you can hit brickwork and instead of penetrating it the drill joggles around and soft plaster gets enlarged to the point where a major tantrum is due
You need to tell us how deep your hole currently is?
Even if you gobbo up the hole and put a rawl plug in and let it set, if there is any weight it will probably bring a nice chunk of plaster off with the shelfs weight!
Drill deeper, bigger rawl plugs, bigger screws may be one option
Sometimes if your unlucky/your drills not much cop/or your mortar bits are not much good, you can hit brickwork and instead of penetrating it the drill joggles around and soft plaster gets enlarged to the point where a major tantrum is due
You need to tell us how deep your hole currently is?
Even if you gobbo up the hole and put a rawl plug in and let it set, if there is any weight it will probably bring a nice chunk of plaster off with the shelfs weight!
Drill deeper, bigger rawl plugs, bigger screws may be one option