Some terminals like xterm allow to redefine the colors via resource files or dynamically, and if it's exposed correctly in the terminfo entry for $TERM, you can do it with:
tput initc 4 1000 0 0
Change ANSI color 4 (normally blue) to RGB (1000, 0 0), that is bright red.
If the terminal doesn't support redefining colours (see infocmp -1 | grep initc), you can also, for applications that use terminfo, trick them into sending different escape sequences to request colour 4 (blue).
infocmp > terminal.info
Edit terminal.info, replace the name of the terminal with something like "myterm", and edit the "setab" property (set ANSI background).
Instead of
setab=\E[4%p1%dm
That is:
tput setab 4
sends ^[[44m, change it to:
setab=\E[4%?%p1%{4}%=%t1%e%p1%d%;m
The %? ...., is an if-then-else, to say send "1" when asked for "4" and the requested one otherwise.
So
tput setab 4
will send ^[[41m, (red) and tput setab 5 will send ^[[45m
Then, compile it with:
TERMINFO=$HOME/.terminfo tic terminal.info
and use it as:
TERMINFO=$HOME/.terminfo TERM=myterm the-application-to-trick
That only works if the application uses the terminfo database to send sequences to the terminal.