I will try to be as detailed as I can. I will UPDATE / MODIFY this post if more clarification is needed.
This is my current NETWORKING hardware:Actiontec C1000A (currently subscribe to CenturyLink with speeds of 20/2)
D'Link DGL-5500 (Router) located on Main Level of home
D'Link DIR-868L (Access Point) located on Second Level of home
HP ProCurve 1810G-8 Network Switch (J9449A) located on Main Level of home
HP ProCurve 1810G-8 Network Switch (J9449A) located on Second Level of home
Here is my current NETWORKING configuration (all connections hardwired using CAT6 ethernet cable) reference my NETWORKING hardware:Actiontec C1000A connected to D'Link DGL-5500 (INTERNET JACK - yellow)
D'Link DGL-5500 (LAN 3) connected to D'Link DIR-868L (LAN 3)
D'Link DGL-5500 (LAN 4) connected to HP ProCurve 1810G-8 Network Switch (Port 1)
D'Link DIR-868L (LAN 4) connected to HP ProCurve 1810G-8 Network Switch (Port 1)
Here is my current NETWORKING configuration (all connections hardwired using CAT6 ethernet cable) reference connected devices:Xbox One (reserved IP address) connected to D'Link DGL-5500 (LAN 1) - Instant On setting enabled
Xbox 360 (reserved IP address) connected to D'Link DGL-5500 (LAN 2)
DirecTv HR34-700 (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 2)
Denon AVR 3311ci (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 3)
58" Panasonic Plasma (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 4)
ADT Home Alarm System connected to HP ProCurve 1810G-8 Network Switch (Port

Xbox One (reserved IP address) connected to D'Link DIR-868L (LAN 1) - Instant On setting enabled
Xbox 360 (reserved IP address) connected to D'Link DIR-868L (LAN 2)
DirecTv HR24-500 (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 2)
DirecTv Genie GO (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 3)
50" Panasonic Plasma (reserved IP address) connected to HP ProCurve 1810G-8 Network Switch (Port 4)
I also have the following devices connected wirelessly to my Home Network:*27" iMac (5Ghz)
*13" MacBook Air (5Ghz)
*(2)iPad 4th Generation (2.4Ghz)
*iPad Mini (2.4Ghz)
*(3) iPhone 5 (2.4Ghz)
*iPhone 5s (2.4GHz)
*(2) Nest Thermostats
*Withings WS-50 Smart Body Analyzer
Prior to our move across town, I had subscribed speeds of 40/5 (CenturyLink Pure Broadband). I was able to get OPEN NAT on both Xbox One consoles with Instant On. After our move (early February) I was only got OPEN NAT on one Xbox One console (first one powered on) if both were powered on with Instant On.
Early this morning, I turned on the Xbox One (main level) and it began a system update. After it completed the system update, I turned on the second Xbox One (second level) and it began a system update. I checked the Network Settings / Current Network Status and determined the Xbox One (main level) had OPEN NAT. After the Xbox One (second level) completed the system update, I checked the Network Settings / Current Network Status and determined the Xbox One (second level) had OPEN NAT.

WHAT!!
I initially thought that maybe because both Xbox One consoles had been reset due to the system update, that this was the reason for both Xbox One consoles displaying OPEN NAT. I DID confirmed that INSTANT ON was still set up like I had it prior to the system update (thought maybe it reset to original out-of-the-box settings). I shut down the Xbox One (second level) and waited 10 seconds, leaving the Xbox One (main level) powered on. I powered on the Xbox One (second level), checked the NETWORK SETTINGS / CURRENT NETWORK STATUS and determined I STILL HAD OPEN NAT on the Xbox One (second level).
I'm not sure if the latest Xbox One console system update pushed out today addressed the issues people were having with only one Xbox One console getting OPEN NAT and all others getting STRICT NAT (when powered on using INSTANT ON). I'm hoping someone else can confirm.
**FYI - Most of you probably have the ENABLE AUTO BANDWIDTH ESTIMATION box checked, I DO NOT. I have the ENABLE AUTO BANDWIDTH ESTIMATION box UNCHECKED. I do have '100' in the Download Speed (Mbps) box, and '10' in the Upload Speed (Mbps) box. FYI**
SO, TO SUM IT UP, I DO HAVE OPEN NAT on BOTH XBOX ONE CONSOLES USING INSTANT ON
[Is this detailed enough Furry?]

Are you using DNS relay or is that disabled and using custom DNS?
Have you adjusted the XB1s in the priority list or just left the priorities alone?
**ENABLE DNS RELAY box is UNCHECKED** (updated 03/05/2014)**Xbox One (main level) has PRIORITY 1 / Xbox One (second level) has PRIORITY 2 << This was my set up after adding the Xbox One consoles to my Home Network a few months ago** (updated 03/05/2014)
MTU 1492 is being used on the router.