@rigor3,
There is no problem. Skype's not exactly intuitive sometimes.
The 'recent' list (which is actually what you are looking at) just shows who you have recently chatted with. Look at the tabs on the left. It defaults to recent. Click on
contacts instead. Then type the first three or so letters of your contact's name in the search bar and it should search your contacts list first.
If you continue to have problems, ask your contact to call you so they end up in your recent list, then right-click and save as a favorite.