SharePoint Administration service (spadminV4),

Error:
This operation uses the SharePoint Administration service (spadminV4), which could not be contacted.

Or

An unexpected internal error occurred in the Business Data Connectivity Shared Service: Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

Got the above error while deploying / redeploying new WSP

Reason:
Basically its a clear cut indication that the one of the required service is un-reachable.

Solution:
There are few things I will recommend you trying

1. Reset all servers in the farm and try once more.

2. Are you trying to deploying using command line , then try UI or vice-versa

3. Login to each box and start services management console. Look for SharePoint Administration service (spadminV4) on each box and restart it. Please make sure to do this on all servers in farm even though you got error on 1 server.

4. This is workaround to kick off jobs without depending upon the failing service, but you can use OLD STSADM command ( stsadm -o execadmsvcjobs ) . Run it on the failing server or all the servers.

5. Also you might have look into Timer Jobs ( waiting mode ). SharePoint creates one timer job for each server. If you see any such job related to Deployment waiting for long time. Delete the job and try redeploying.

Other related posts:
Deployment stuck at retracting message , Deployment stuck at retracting message