It's definitely the saddle. Even if if means, wastefully, buying two, three, or four saddles, in the end, do it. It is important that you protect yourself there. It can lead to nerve and back problems. It's an absolute pleasure when a seat just fits right. Basically, you want a seat that will not put any pressure on your perineum-area, at all. Find an ergonomically -shaped seat for your particular derriere, and spare no expense on the choosing the right one. I bought three in the end. Here's the Selle Italia site, expect to pay £50 - £100ish for one that will be right for you. I got mine for £35, but is normally £50. Shopping around is worth it. I'm sure immatfaal will give you tips on what yo look for. The Lady Man Gel flow looks good...will be about £100 for the Gel Flow range. Have a gander through the whole site... they are saddle specialists. My Selle Royal Respiro is fab... It will go on every bike I buy.
http://www.selleitalia.com/en/prodotti/road/
A bike with a more sporty rider position is easier in the long run for riding but you still have to buy a saddleand seat on top to make it comfortable, for you
Choose your grips, as well, with the same scrutiny if you are get a heavy, localised pressure-ache in your hands, after a while, with your current ones. You want grips that spread the load from your leaning over, on as much palm area as possible. Here's the Ergon site. If you do fancy any of those, let me know, and I'll let you know the ins-and-outs of the model codes within each type. The prices are about the same as the seats.
http://www.ergon-bike.com/us/en/home
A bike with a more sporty rider position is easier in the long run for riding log-distance, and hills, but you will still have to buy a saddleand seat on top to make it optimally comfortable, for you. If the pedal size is a bit mean on your bike, change them as well.