A gate resistor is basically intended to keep the circuit stable and prevent what are called "parasitic oscilations". Bychon is correct that these resistors need to be small in value...
It does sound as if the mosfet isn't turning on all the way, the specs on this device tell me that you probably need to select something that will work on 5V rails as this mosfet really requires a higher voltage to fully snap on or off. Still, don't be afraid to experiment, that's how we all learn!
Mad Soundman