I'm surprised you couldn't run it from a terminal:
$ which redhat-config-printer
But machts nichts - you found the right one anyway (same program).
From there, do as you did up until you selected "Networked Windows (SMB)". Click on "Select" (if you don't see your remote printer) and enter the information in there. The reason it may not immediately find the remote printer are varied and too numerous to list here, but this should get you going in the right direction. I can't help any further because I don't have any Windows boxes to check against.