Try this:

PS4:

Step 1: ​Turn off the PlayStation 4 by pressing the power button on the front panel. The power indicator will blink for a few moments before turning off.
Step 2: ​Once the PlayStation 4 is off, press and hold the power button. Release it after you’ve heard two beeps: one when you initially press, and another 7 seconds later.
Step 3: ​Connect the DualShock 4 controller with the provided USB cable and press the PS button on the controller.
Step 4: From the list of options select Rebuild Database and press “X”. Once the process is complete the PS4 will restart.​
Step 5: Run the Internet connection test at [Settings] > [Network] > [Test Internet Connection] and make sure you can connect to the network.​

PS3:

1. Turn off your PS3.
2. Hold down the power button and wait for your PS3 to turn on and off.
3. Once it has turned off, hold the power button until you hear 2 beeps.
4. When you hear the 2 beeps let go of the power button.
5. Plug in your controller and press the PS button.
6. The Recovery menu should be on your screen now!

Select Rebuild Database for both devices. See if that works.

I've tried the PS4 step, internet connection is fine however PSN FAILS to connect...

- The same on PS3

Try disabling the media servers in Settings.

Nothing

Try holding down the reset button on the back of your router for 30 seconds. It should change your IP Address. If it doesn't, then call up your ISP and tell them you want your IP Address changed.

Unfortunately that hasn't change my IP! I'll have to call up tomorrow :/

Thanks! I'll update everyone when I get it sorted

Alright, sounds good. Keep us updated

Thanks for staying with me throughout this process <3