Issues with SQL Deadlocks and sluggish system

We've been having a whale of a time determining why, all of a sudden, we're getting SQL Deadlocks and extreme slowness in our website. I upped the max_connections to alleviate some "Out of Connections" error we had as well.

I have the following in my.cnf

[mysqld]
port		= 3306
socket		= /var/lib/mysql/mysql.sock
skip-locking
key_buffer = 16M
max_allowed_packet = 1M
table_cache = 64
sort_buffer_size = 512K
net_buffer_length = 8K
read_buffer_size = 256K
read_rnd_buffer_size = 512K
myisam_sort_buffer_size = 8M
max_connections = 150

[mysqldump]
quick
max_allowed_packet = 16M

[isamchk]
key_buffer = 20M
sort_buffer_size = 20M
read_buffer = 2M
write_buffer = 2M

[myisamchk]
key_buffer = 20M
sort_buffer_size = 20M
read_buffer = 2M
write_buffer = 2M

We are using ExpressionEngine and Magento, and I know Magento is a database hog and is the ONLY source of the SQL Deadlocks as it is occuring in Magento's PDO.php file when a customer update is being performed.

#0 /store/lib/Zend/Db/Statement.php(300): Zend_Db_Statement_Pdo->_execute(Array)
#1 /store/lib/Zend/Db/Adapter/Abstract.php(468): Zend_Db_Statement->execute(Array)
#2 /store/lib/Zend/Db/Adapter/Pdo/Abstract.php(238): Zend_Db_Adapter_Abstract->query('UPDATE `magcust...', Array)
#3 /store/lib/Varien/Db/Adapter/Pdo/Mysql.php(333): Zend_Db_Adapter_Pdo_Abstract->query('UPDATE `magcust...', Array)
#4 /store/lib/Zend/Db/Adapter/Abstract.php(604): Varien_Db_Adapter_Pdo_Mysql->query('UPDATE `magcust...', Array)
#5 /store/app/code/core/Mage/Eav/Model/Entity/Abstract.php(1133): Zend_Db_Adapter_Abstract->update('magcustomer_ent...', Array, 'entity_id='9170...')
#6 /store/app in /srv/www/htdocs/store/lib/Zend/Db/Statement/Pdo.php on line 235

We authenticate our users through our ERP using a web service and have everyone's Magento account have the same password so that we can log them in automatically. We update their Magento record when we authenticate.

I added code to retry when a deadlock was found but that only caused the system to slow down even more. So, what do you think may be causing our issues?  

Here is also the uncommented variables in my PHP .ini file:

zend.ze1_compatibility_mode = Off
short_open_tag = On
asp_tags = Off
precision    =  14
y2k_compliance = On
output_buffering = 4096
zlib.output_compression = Off
implicit_flush = Off
unserialize_callback_func=
serialize_precision = 100
allow_call_time_pass_reference = Off
safe_mode = Off
safe_mode_gid = Off
safe_mode_include_dir =
safe_mode_exec_dir =
safe_mode_allowed_env_vars = PHP_
safe_mode_protected_env_vars = GCONV_PATH,GETCONF_DIR,HOSTALIASES,LD_AUDIT,LD_DEBUG,LD_DEBUG_OUTPUT,LD_DYNAMIC_WEAK,LD_LIBRARY_PATH,LD_ORIGIN_PATH,
         LD_PRELOAD,LD_PROFILE,LD_SHOW_AUXV,LD_USE_LOAD_BIAS,LOCALDOMAIN,LOCPATH,MALLOC_TRACE,NLSPATH,RESOLV_HOST_CONF,RES_OPTIONS,TMPDIR,TZDIR
disable_functions =
disable_classes =
expose_php = On

max_execution_time = 60     ; Maximum execution time of each script, in seconds
max_input_time = 60	        ; Maximum amount of time each script may spend parsing request data
memory_limit = 1024M        ; Maximum amount of memory a script may consume (128MB)
error_reporting  =  E_ALL

display_errors = Off
display_startup_errors = Off
log_errors = On
log_errors_max_len = 1024
ignore_repeated_errors = Off
ignore_repeated_source = Off
report_memleaks = On
track_errors = Off
html_errors = Off
error_log = /var/tmp/php_error.log
variables_order = "GPCS"
register_globals = Off
register_long_arrays = Off
register_argc_argv = Off
auto_globals_jit = On
post_max_size = 20M

magic_quotes_gpc = Off
magic_quotes_runtime = Off
magic_quotes_sybase = Off
auto_append_file =

default_mimetype = "text/html"
default_charset = "UTF-8"

include_path = ".:/usr/share/php5:/usr/share/php5/PEAR"
doc_root =
user_dir =
extension_dir = /usr/lib64/php5/extensions
enable_dl = Off

file_uploads = On
upload_tmp_dir = "/tmp"
upload_max_filesize = 20M

allow_url_fopen = On
allow_url_include = Off
default_socket_timeout = 60

define_syslog_variables  = Off

sql.safe_mode = Off

odbc.allow_persistent = Off
odbc.check_persistent = On
odbc.max_persistent = -1
odbc.max_links = -1
odbc.defaultlrl = 4096
odbc.defaultbinmode = 1

mysql.allow_persistent = Off
mysql.max_persistent = -1
mysql.max_links = -1
mysql.default_port =

mysql.default_socket =
mysql.default_host =
mysql.default_user =
mysql.default_password =

mysql.connect_timeout = 60
mysql.trace_mode = Off

mysqli.max_links = -1
mysqli.default_port = 3306
mysqli.default_socket =

mysqli.default_host =
mysqli.default_user =
mysqli.default_pw =

mysqli.reconnect = Off

session.save_handler = files

session.save_path = "/var/lib/php5"
session.use_cookies = 1
session.use_only_cookies = 1
session.name = PHPSESSID
session.auto_start = 0
session.cookie_lifetime = 0
session.cookie_path = /
session.cookie_domain =
session.cookie_httponly = 1
session.serialize_handler = php
session.gc_probability = 1
session.gc_divisor     = 1000
session.gc_maxlifetime = 1440
session.bug_compat_42 = 0
session.bug_compat_warn = 1
session.referer_check =
session.entropy_length = 16
session.entropy_file = /dev/urandom
session.cache_limiter = nocache
session.cache_expire = 180
session.use_trans_sid = 0
session.hash_function = 1
session.hash_bits_per_character = 5
url_rewriter.tags = "a=href,area=href,frame=src,input=src,form=fakeentry"


soap.wsdl_cache_enabled=1
soap.wsdl_cache_dir="/tmp"
soap.wsdl_cache_ttl=86400