Yes you need to rebuild your App using the new mobile provisioning profile but there is no need to update the APNS certificates ..
You'll also need to make sure you have enabled 'Preflight' in your Developer App to be able to test / receive push notifications.
Once done and the App re-installed on device, it should ask you whether or not you elect to receive notifications and you can test again.