You might actually be doing something different than what you think. "Increasing flash power" would mean creating higher light intensity for the same amount of time. However, with some flashes, "increasing flash power" just means the same amount of energy being radiated, just in a shorter amount of time.
To show the difference: the first case you would burn 2 candles instead of 1 candle for 1 seconds. The second case, you burn two candles for half second instead of 1 candle for one second.
So basically, what I think is: you have the latter type of flash. Which means that if you try to increase flash power, it will radiate the same energy in a shorter amount of time. However, if your camera is not in sync with that (the shutter is not in sync with the flash) then you will get underexposure. And obviously, if you are underexposed, you will get blur whatever you do with your aperture or shutter speed.
Probably you are just getting a fraction of the real power of your flash.
The real test for this is: go into a dark room (completely dark), change to long exposure mode (BULB), and manually trigger a flash, then finish shooting. Then switch to your shutter setting, and make another picture. Now, because the flash emission is very rapid, you should see exactly the same picture! (Basically the flash "freezes" the shot). If you do not, you have the problem I described. (You may want to switch to Manual focus, to avoid infinite focus hunting in the dark...)