Your role instances have recycled a number of times during an update or upgrade operation. This indicates that the new version of your service or the configuration settings you provided when configuring the service prevent the role instances from running. Verify your code does not throw unhandled exceptions and that your configuration settings are correct and then start another update or upgrade operation

After many days and countless hours of bug-hunting, hair-pulling & nail-biting, it turns out the cause of this error was from the 'Create Storage Connection String' dialogue window on the 'Caching' tab of  the properties page of the WebRole for my WindowsAzure website project.
 
Under 'Specify the storage account credentials to use for maintaining the cache cluster's runtime state', and then under 'Connect using:'

even after I've selected the second option, 'Your subscription' (where I specify the correct AccountKey) - whenever I re-enter this dialogue I notice the selected option seems to keep reverting back to the last option 'Manually entered credentials', which is using an incorrect AccountKey value. In this window it's fairly easy to see, even just from the first few characters of the AccountKey (green circles), that they no longer match up!

Ultimately, the upshot of this is that the Webrole's Run() method will throw an unhandled exception while you're attempting to deploy the app to Azure, causing the Webrole to recycle indefinitely, and thereby causing all deploy attempts to fail.

 So I know now it's always worth checking each time before a deploy to make sure that the correct 'Connect using:' option for Caching Storage Connection String is selected on this dialogue window!



Microsoft's warning:

more info here: http://msdn.microsoft.com/en-us/library/ee405486.aspx