I'm currently asking RIM about some of these, here are the first thoughts which may or may not help. First, make sure that MDAC 2.8 is installed on the BES server and the database server if it's a remote database. Also, they suggest enabling network protocols of "Named Pipes" and "TCP/IP " in SQL server network utility on the computer hosting the BlackBerry server configuration database. To open SQL server network utility, type "svrnetcn" from the run menu.
If a device is not on 4.0, it will create more errors in the log.
Some of this is already in the 4.0 installation documentation, but there may be something that helps get rid of an error or two.