So went out to run an errand after driving it that morning and the shifter will not come out of park. Removed the cover and pressed the override button down and it will shift out of park. Researched on this forum and replaced the Brake Shift Interlock Solenoid but it still will not release. I'm open to ideas, any help would be appreciated.

The problem is never the solenoid, it's always the switch that activates it. These will probably help you out:
https://www.thenissanpath.com/topic21291.html
https://www.nicoclub.com/archives/help- ... e-fix.html

So I was finally able to get the micro switch from Digi-key and replaced the switch. Still will not shift out of park AND now the truck will not start with the key fob. I have to release the physical key and insert it in the ignition switch to get it to start. I'm open to ideas.

1) Are you sure you replaced the right switch? The detente switch in the shifter is generally wired NC instead of NO and will cause I-key issues if it's replaced incorrectly. If you trace the wires, the solenoid switch will wire to the solenoid and ground, the detente switch will wire to either the shift handle or direct to the shifter connector.
2) Most of the early I-key setups with faux key cylinders instead of a button have a cable connecting the cylinder to the shifter, and if it's out of adjustment it can prevent proper operation of the cylinder and fob.

If that's all good, do some old school diag on your repair. The shift solenoid gets power through the brake switch on the high side, make sure the power is getting there. On most shifters the solenoid coil will read at least 20 ohms, and the low side of the solenoid will show a good ground in the Park position if the switch is working properly.

1) I double checked my order and it looks like I ordered the wrong micro switch. I ordered the Omron ‎SS-5GL13‎ today. So it will be here in 3-4 days.
*** I am no electrician but I try my best, can you explain what you mean by NC instead of NO ? I can tell you I took a picture of the wires connected to the old switch and I put the wires on the new switch in exactly the same position.

Most of those microswitches are SPDT (single-pole double-throw), and they have an NC (normally closed) contact and an NO (normally open) contact. The throws are usually marked on the switch housing, along with the common (COM) terminal. The detente switches usually use the throw COM-NC, while the solenoid switches use the throw COM-NO.