This is no big deal since replacement batteries don;t cost that much.
One thing that batteries do when they begin to fail is that they swell up, just a bit. Take the battery out and run your fingers over the two large flat sides (top and bottom). If the battery does not feel flat (there is a little bulge) - especially in the center then, the battery is suspect. Please check this.
Does the phone charge? When you go to Options, Device, Device and Status Information what is the battery charge percentage? You can get the same result by typing <Alt><LeftShift>H
When you plug the phone into the wall charger, do you see the charge symbol by the battery?
You should not need a piece of paper to hold the battery in place. This makes me wonder if you have the correct battery in your phone. Is the phone new? If you do not mind me asking where did you buy it?
The more information you provide, the higher quality will be the response so, please update your profile so we can all see which carrier you are on and what part of the world you are in.