I had this issue and tried all of the above but nothing worked. Then I fixed it! You do need to change the width under the branding div like dazzyweb said but make sure you check the URL of the header logo. It may be automatically refering to a resized version.
Go to:
-Appearance
-Theme Settings
Then check where it says logo. If you clicked upload and uploaded the logo there take a look at the end of the url. It may say something like:
https://www.yoursite.com/wp-content/uploads/2013/12/LOGO-300×37.jpg
This is referring to a resized version of the logo you uploaded. Take off the dimensions they added so that it looks more like:
https://www.yoursite.com/wp-content/uploads/2013/12/LOGO.jpg
This will give you the full resolution of the logo you uploaded. Now you can adjust the size by changing the width like dazzyweb originally stated. I hope this helps someone!
