I was looking to play a game I played when I was younger, but I can't remember the name or too much about the game.

The main character is a Ninja.
It has an overworld to travel on.
Whenever you went to a castle, you had options to infiltrate or perform reconnaissance.
If you chose either option, I remember a cut scene to where it showed the wall of the castle, and your character trying to climb up.
The game is on the NES.

Does this sound familiar to anyone? 

You're thinking of Inindo: Way of the Ninja. When you failed to infiltrate the castle, your guy would slide down the wall, and you wasted a day. If you succeeded in sabotage, you got a cutscene of the place burning, and if you infiltrated, you just drop into a room.

 It was actually one of the first SNES games, which is why it looked like an NES game. It's a decent RPG; it's certainly unique in that it merges a JRPG with Koei's strategy games.

It was ported from the PC/MSX2 console which is why it looked like a NES game.

This game was extremely unpolished, but it's dynamic and somewhat emergent gameplay was and is still a unique element to console games. Heck it's unique even among PC gaming.

Thanks. I remember the name now.