I'm on Lion 10.7.2 and still having the same problem reported above - two tries are necessary to log in to the VPN. Since I didn't have this problem on Snow Leopard using the same server and same client-side parameters, isn't this a Mac OS regression?
Here's an extract of system.log which may help in diagnosing the problem (with host name changed to vpn.xxxxxx.com for protection and server address changed to 65.xxx.xx.x). The log entry with timestamp Nov 24 19:47:13 is where I manually disconnected and then re-tried:
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec connecting to server vpn.xxxxxx.com
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro configd[16]: SCNC: start, triggered by SystemUIServer, type IPSec, status 0
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec Phase1 starting.
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec connecting to server 65.xxx.xx.x
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Phase1 started (Initiated by me).
Nov 24 19:47:12 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit success. (Initiator, Aggressive-Mode message 1).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKEv1 Phase1 AUTH: success. (Initiator, Aggressive-Mode Message 2).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: receive success. (Initiator, Aggressive-Mode message 2).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKEv1 Phase1 Initiator: success. (Initiator, Aggressive-Mode).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit success. (Initiator, Aggressive-Mode message 3).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Phase1 established (Initiated by me).
Nov 24 19:47:13 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Extended Authentication requested.
Nov 24 19:47:32 Glyn-Normingtons-MacBook-Pro configd[16]: SCNC: stop, type IPSec
Nov 24 19:47:32 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec disconnecting from server 65.xxx.xx.x
Nov 24 19:47:32 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit failed. (Information message).
Nov 24 19:47:32 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKEv1 Information-Notice: transmit failed. (Delete ISAKMP-SA).
Nov 24 19:47:32 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec disconnecting from server 65.xxx.xx.x
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec connecting to server vpn.******.com
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro configd[16]: SCNC: start, triggered by SystemUIServer, type IPSec, status 0
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec Phase1 starting.
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec connecting to server 65.xxx.xx.x
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro racoon[1393]: Connecting.
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Phase1 started (Initiated by me).
Nov 24 19:47:37 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit success. (Initiator, Aggressive-Mode message 1).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKEv1 Phase1 AUTH: success. (Initiator, Aggressive-Mode Message 2).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: receive success. (Initiator, Aggressive-Mode message 2).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKEv1 Phase1 Initiator: success. (Initiator, Aggressive-Mode).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit success. (Initiator, Aggressive-Mode message 3).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Phase1 established (Initiated by me).
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro racoon[1393]: IPSec Extended Authentication requested.
Nov 24 19:47:38 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec requesting Extended Authentication.
Nov 24 19:47:47 Glyn-Normingtons-MacBook-Pro configd[16]: IPSec sending Extended Authentication.
Nov 24 19:47:47 Glyn-Normingtons-MacBook-Pro racoon[1393]: IKE Packet: transmit success. (Mode-Config message).