Upgrade my Rear Cassette from 12/25t to 11/28t
Usually, the up to 26t is more so a guideline than a hard limit as is the chain wrap capacity. I'd say try the 11/28t - it will probably work, and if it doesn't work you can always put a new long cage Shimano derailleur (such as a deore one - the cable issues dont matter for road vs mountain rd's from Shimano, or a Sora if you want to stick with the road group). Of course, if you don't shift properly, there is a higher risk of things not working the way they should. 

Though, you probably just need to spin faster instead of higher gearing (use Sheldon Brown's gearing calculator to see the differences): http://sheldonbrown.com/gears/