You should be able to generate the appropriate rename scripts using this, and adjust it to whatever naming convention you choose; I've used this to ensure that the names use the current table and column names, so the where clause currently finds names that don't follow that convention.
SELECT
PK_Table = PK.TABLE_NAME,
PK_Column = PT.COLUMN_NAME,
FK_Table = FK.TABLE_NAME,
FK_Column = CU.COLUMN_NAME,
Constraint_Name = C.CONSTRAINT_NAME,
'FK_' + FK.TABLE_NAME + '_' + PK.TABLE_NAME + '_' + CU.COLUMN_NAME,
'sp_rename ''' + C.CONSTRAINT_NAME + ''', ' + '''FK_' + FK.TABLE_NAME + '_' + PK.TABLE_NAME + '_' + CU.COLUMN_NAME + '''' + char(13) + char(10) + 'GO' + CHAR(13) + CHAR(10)
FROM
INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS C
INNER JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS FK ON C.CONSTRAINT_NAME = FK.CONSTRAINT_NAME
INNER JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS PK ON C.UNIQUE_CONSTRAINT_NAME = PK.CONSTRAINT_NAME
INNER JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE CU ON C.CONSTRAINT_NAME = CU.CONSTRAINT_NAME
INNER JOIN (
SELECT i1.TABLE_NAME, i2.COLUMN_NAME
FROM INFORMATION_SCHEMA.TABLE_CONSTRAINTS i1
INNER JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE i2 ON i1.CONSTRAINT_NAME = i2.CONSTRAINT_NAME
WHERE i1.CONSTRAINT_TYPE = 'PRIMARY KEY'
) PT ON PT.TABLE_NAME = PK.TABLE_NAME
WHERE
C.CONSTRAINT_NAME != 'FK_' + FK.TABLE_NAME + '_' + PK.TABLE_NAME + '_' + CU.COLUMN_NAME
ORDER BY
PK.TABLE_NAME, FK.TABLE_NAME
sp_rename. This will let you rename objects in-place instead of having to drop and recreate everything. – Jon Seigel Jan 18 at 14:34