i am having the exact same problem. This morning saw someone posted a workaround in FB ps4 msia group, the steps are more or less as below
1. disable ipv6 on your router
2. use custom dns, such as openDNS, google DNS and etc
according to the OP, it may affect your dl speed, he mentioned he is on 500mbps plan and he only manage to get less than 10mbps after doing above steps, but at least he manage to get nat 2 until this issue resolve by TM
edit : OP posted an update, he tried using default settings on router aka using TM dns by default and it works as well.
This post has been edited by darude87: Feb 17 2020, 10:30 AM
Ps4 Nat type failed
Feb 17 2020, 10:23 AM
Quote
0.0158sec
0.43
7 queries
GZIP Disabled