Multiple Navigation Nodes Problem and Navigation Deadlock in SharePoint 2010

Symtoms:
Issue happens after  August 2012 CU installed for SharePoint Server 2010.

After publishing a new page the site load times start to increase dramatically or page requests don’t finish loading at all. You will see the infamous “An expected error has occurred“-error or if the callstack is enabled and custom errors are turned off in the web.config (CallStack=”true” / customErrors mode=”Off”) you will see a “Request timed out.” error-message.

System.Data.SqlClient.SqlException: Transaction (Process ID 76) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction. at System.Data.SqlClient.SqlConnection.OnError(SqlException exception, Boolean breakConnection)
at System.Data.SqlClient.TdsParser.ThrowExceptionAndWarning(TdsParserStateObject stateObj)
at System.Data.SqlClient.TdsParser.Run(RunBehavior runBehavior, SqlCommand cmdHandler, SqlDataReader dataStream, BulkCopySimpleResultSet bulkCopyHandler, TdsParserStateObject stateObj)
at System.Data.SqlClient.SqlDataReader.HasMoreRows()
at System.Data.SqlClient.SqlDataReader.ReadInternal(Boolean setTimeout)
at Microsoft.SharePoint.SPSqlClient.ExecuteQueryInternal(Boolean retryfordeadlock)
at Microsoft.SharePoint.SPSqlClient.ExecuteQuery(Boolean retryfordeadlock)

PortalSiteMapProvider was unable to fetch children for node at URL: /<site>, message: An unexpected error occurred while manipulating the navigational structure of this Web., stack trace:
at Microsoft.SharePoint.SPGlobal.HandleComException(COMException comEx)
at Microsoft.SharePoint.Library.SPRequest.UpdateNavigationNode(String bstrUrl, Int32 lNodeId, DateTime dateParented, String bstrName, String bstrNodeUrl, Object& pvarProperties, String& pbstrDateModified)
at Microsoft.SharePoint.Navigation.SPNavigationNode.Update()

Resolution:
 SharePoint April 2013 CU

For more details and for workarounds :
http://blogs.msdn.com/b/joerg_sinemus/archive/2013/02/12/february-2013-sharepoint-2010-hotfix.aspx