There's not enough code here to know what the problem is. It looks like what you posted is correct, but the ball won't actually change direction until the next execution of move() occurs. It's possible that you are reinitializing your velocity variables before the next move(). Did you declare them before or inside the while loop?
You need to trace through the code and see what is happening to your velocity vars between the detect collision call above and the next call to move(). Also, have you verified that the code above is actually executing the
if (collision == paddle) velocity_y = -velocity_y; code? Maybe insert a printf statement?
There are just too many ways this could be happening. If the above isn't the issue, you need to post the entire while loop at minimum.
If this answers your question, please click the check mark to accept. Let's keep up on frum maintenance.