diff --git a/src/table.c b/src/table.c
index f51ad81..f1ea798 100644
--- a/src/table.c
+++ b/src/table.c
@@ -36,7 +36,7 @@
 #define _vte_table_is_numeric(__c) \
 	(((__c) >= '0') && ((__c) <= '9'))
 #define _vte_table_is_numeric_list(__c) \
-	((((__c) >= '0') && ((__c) <= '9')) || (__c) == ';')
+	((((__c) >= '0') && ((__c) <= '9')) || (__c) == ';' || (__c) == ':')
 
 struct _vte_table {
 	struct _vte_matcher_impl impl;
@@ -463,7 +463,7 @@ _vte_table_matchi(struct _vte_table *table,
 		const char *local_result;
 
 		subtable = table->table_number_list;
-		/* Iterate over all numeric characters and ';'. */
+		/* Iterate over all numeric characters, ';' and ':'. */
 		for (i = 1; i < length; i++) {
 			if (!_vte_table_is_numeric_list(candidate[i])) {
 				break;
@@ -536,6 +536,8 @@ _vte_table_extract_numbers(GValueArray **array,
 			   struct _vte_table_arginfo *arginfo, long increment)
 {
 	GValue value = {0,};
+	GValue subvalue = {0,};
+	GValueArray *subarray = NULL;
 	gssize i;
 
         if (G_UNLIKELY (*array == NULL)) {
@@ -543,16 +545,31 @@ _vte_table_extract_numbers(GValueArray **array,
         }
 
 	g_value_init(&value, G_TYPE_LONG);
+	g_value_init(&subvalue, G_TYPE_VALUE_ARRAY);
 	i = 0;
 	do {
 		long total = 0;
-		for (; i < arginfo->length && arginfo->start[i] != ';'; i++) {
+		for (; i < arginfo->length && arginfo->start[i] != ';' && arginfo->start[i] != ':'; i++) {
 			gint v = g_unichar_digit_value (arginfo->start[i]);
 			total *= 10;
 			total += v == -1 ?  0 : v;
 		}
 		g_value_set_long(&value, CLAMP (total, 0, G_MAXUSHORT));
-		g_value_array_append(*array, &value);
+		if (i < arginfo->length && arginfo->start[i] == ':') {
+			if (subarray == NULL) {
+				subarray = g_value_array_new(2);
+			}
+			g_value_array_append(subarray, &value);
+		} else {
+			if (subarray == NULL) {
+				g_value_array_append(*array, &value);
+			} else {
+				g_value_array_append(subarray, &value);
+				g_value_set_boxed(&subvalue, subarray);
+				g_value_array_append(*array, &subvalue);
+				subarray = NULL;
+			}
+		}
 	} while (i++ < arginfo->length);
 	g_value_unset(&value);
 }
@@ -859,6 +876,9 @@ print_array(GValueArray *array)
 				printf("\"%ls\"",
 				       (wchar_t*) g_value_get_pointer(value));
 			}
+			if (G_VALUE_HOLDS_BOXED(value)) {
+				print_array(g_value_get_boxed(value));
+			}
 		}
 		printf(")");
 		/* _vte_matcher_free_params_array(array); */
@@ -878,6 +898,12 @@ main(int argc, char **argv)
 		"]3;fook",
 		"[3;foo",
 		"[3;3m",
+		"[3;5;42m",
+		"[3;5:42m",
+		"[3:5:42m",
+		"[3;2;110;120;130m",
+		"[3;2:110:120:130m",
+		"[3:2:110:120:130m",
 		"[3;3mk",
 		"[3;3hk",
 		"[3;3h",
@@ -901,9 +927,7 @@ main(int argc, char **argv)
 	_vte_table_add(table, "ACDEF%sJ", 8, "ACDEF%sJ", 0);
 	_vte_table_add(table, "ACDEF%i%mJ", 10, "ACDEF%dJ", 0);
 	_vte_table_add(table, "[%mh", 5, "move-cursor", 0);
-	_vte_table_add(table, "[%d;%d;%dm", 11, "set-graphic-rendition", 0);
-	_vte_table_add(table, "[%dm", 5, "set-graphic-rendition", 0);
-	_vte_table_add(table, "[m", 3, "set-graphic-rendition", 0);
+	_vte_table_add(table, "[%mm", 5, "character-attributes", 0);
 	_vte_table_add(table, "]3;%s", 7, "set-icon-title", 0);
 	_vte_table_add(table, "]4;%s", 7, "set-window-title", 0);
 	printf("Table contents:\n");
diff --git a/src/vteseq.c b/src/vteseq.c
index d0c6ac4..d740f5e 100644
--- a/src/vteseq.c
+++ b/src/vteseq.c
@@ -2331,7 +2331,54 @@ vte_sequence_handler_vs (VteTerminal *terminal, GValueArray *params)
 						 visible. */
 }
 
-/* Handle ANSI color setting and related stuffs (SGR). */
+/* Parse parameters of SGR 38 or 48, starting at @index within @params.
+ * Returns the color index, or -1 on error.
+ * Increments @index to point to the last consumed parameter (not beyond). */
+static gint32
+vte_sequence_parse_sgr_38_48_parameters (GValueArray *params, unsigned int *index)
+{
+	if (*index < params->n_values) {
+		GValue *value0, *value1, *value2, *value3;
+		long param0, param1, param2, param3;
+		value0 = g_value_array_get_nth(params, *index);
+		if (G_UNLIKELY (!G_VALUE_HOLDS_LONG(value0)))
+			return -1;
+		param0 = g_value_get_long(value0);
+		switch (param0) {
+		case 2:
+			if (G_UNLIKELY (*index + 3 >= params->n_values))
+				return -1;
+			value1 = g_value_array_get_nth(params, *index + 1);
+			value2 = g_value_array_get_nth(params, *index + 2);
+			value3 = g_value_array_get_nth(params, *index + 3);
+			if (G_UNLIKELY (!(G_VALUE_HOLDS_LONG(value1) && G_VALUE_HOLDS_LONG(value2) && G_VALUE_HOLDS_LONG(value3))))
+				return -1;
+			param1 = g_value_get_long(value1);
+			param2 = g_value_get_long(value2);
+			param3 = g_value_get_long(value3);
+			if (G_UNLIKELY (param1 < 0 || param1 >= 256 || param2 < 0 || param2 >= 256 || param3 < 0 || param3 >= 256))
+				return -1;
+			*index += 3;
+			return (1 << 24) | (param1 << 16) | (param2 << 8) | param3;
+		case 5:
+			if (G_UNLIKELY (*index + 1 >= params->n_values))
+				return -1;
+			value1 = g_value_array_get_nth(params, *index + 1);
+			if (G_UNLIKELY (!G_VALUE_HOLDS_LONG(value1)))
+				return -1;
+			param1 = g_value_get_long(value1);
+			if (G_UNLIKELY (param1 < 0 || param1 >= 256))
+				return -1;
+			*index += 1;
+			return param1;
+		}
+	}
+	return -1;
+}
+
+/* Handle ANSI color setting and related stuffs (SGR).
+ * @params contains the values split at semicolons, with sub arrays splitting at colons
+ * wherever colons were encountered. */
 static void
 vte_sequence_handler_character_attributes (VteTerminal *terminal, GValueArray *params)
 {
@@ -2342,8 +2389,33 @@ vte_sequence_handler_character_attributes (VteTerminal *terminal, GValueArray *p
 	param = 0;
 	/* Step through each numeric parameter. */
 	for (i = 0; (params != NULL) && (i < params->n_values); i++) {
-		/* If this parameter isn't a number, skip it. */
 		value = g_value_array_get_nth(params, i);
+		/* If this parameter is a GValueArray, it can be a fully colon separated 38 or 48
+		 * (see below for details). */
+		if (G_UNLIKELY (G_VALUE_HOLDS_BOXED(value))) {
+			GValueArray *subvalues = g_value_get_boxed(value);
+			GValue *value0;
+			long param0;
+			gint32 color;
+			unsigned int index = 1;
+
+			value0 = g_value_array_get_nth(subvalues, 0);
+			if (G_UNLIKELY (!G_VALUE_HOLDS_LONG(value0)))
+				continue;
+			param0 = g_value_get_long(value0);
+			if (G_UNLIKELY (param0 != 38 && param0 != 48))
+				continue;
+			color = vte_sequence_parse_sgr_38_48_parameters(subvalues, &index);
+			if (G_LIKELY (color != -1)) {
+				if (param0 == 38) {
+					terminal->pvt->screen->defaults.attr.fore = color;
+				} else {
+					terminal->pvt->screen->defaults.attr.back = color;
+				}
+			}
+			continue;
+		}
+		/* If this parameter is not a GValueArray and not a number either, skip it. */
 		if (!G_VALUE_HOLDS_LONG(value)) {
 			continue;
 		}
@@ -2414,55 +2486,36 @@ vte_sequence_handler_character_attributes (VteTerminal *terminal, GValueArray *p
 		case 38:
 		case 48:
 		{
-			/* The format looks like: ^[[38;5;COLORNUMBERm or ^[[38;2;RED;GREEN;BLUEm
-			   so look for the parameters here. */
+			/* The format looks like:
+			 * - 256 color indexed palette:
+			 *   - ^[[38;5;INDEXm
+			 *   - ^[[38;5:INDEXm
+			 *   - ^[[38:5:INDEXm
+			 * - true colors:
+			 *   - ^[[38;2;RED;GREEN;BLUEm
+			 *   - ^[[38;2:RED:GREEN:BLUEm
+			 *   - ^[[38:2:RED:GREEN:BLUEm
+			 * See bug 685759 for details.
+			 * The fully colon versions were handled above separately. The code is reached
+			 * if the first separator is a semicolon. */
 			if ((i + 1) < params->n_values) {
-				GValue *value1, *value2, *value3, *value4;
-				long param1, param2, param3, param4;
-				value1 = g_value_array_get_nth(params, i + 1);
-				if (G_UNLIKELY (!G_VALUE_HOLDS_LONG(value1)))
-					break;
-				param1 = g_value_get_long(value1);
-				switch (param1) {
-				case 2:
-					if (G_UNLIKELY ((i + 4) >= params->n_values))
-						break;
-					value2 = g_value_array_get_nth(params, i + 2);
-					value3 = g_value_array_get_nth(params, i + 3);
-					value4 = g_value_array_get_nth(params, i + 4);
-					if (G_UNLIKELY (!(G_VALUE_HOLDS_LONG(value2) && G_VALUE_HOLDS_LONG(value3) && G_VALUE_HOLDS_LONG(value4))))
-						break;
-					param2 = g_value_get_long(value2);
-					param3 = g_value_get_long(value3);
-					param4 = g_value_get_long(value4);
-					if (G_LIKELY (param2 >= 0 && param2 < 256 && param3 >= 0 && param3 < 256 && param4 >= 0 && param4 < 256)) {
-						guint32 value = (1 << 24) | (param2 << 16) | (param3 << 8) | param4;
-						if (param == 38) {
-							terminal->pvt->screen->defaults.attr.fore = value;
-						} else {
-							terminal->pvt->screen->defaults.attr.back = value;
-						}
-					}
-					i += 4;
+				gint32 color;
+				GValue *value1 = g_value_array_get_nth(params, ++i);
+				if (G_VALUE_HOLDS_LONG(value1)) {
+					color = vte_sequence_parse_sgr_38_48_parameters(params, &i);
+				} else if (G_VALUE_HOLDS_BOXED(value1)) {
+					GValueArray *subvalues = g_value_get_boxed(value1);
+					unsigned int index = 0;
+					color = vte_sequence_parse_sgr_38_48_parameters(subvalues, &index);
+				} else {
 					break;
-				case 5:
-					if (G_UNLIKELY ((i + 2) >= params->n_values))
-						break;
-					value2 = g_value_array_get_nth(params, i + 2);
-					if (G_UNLIKELY (!G_VALUE_HOLDS_LONG(value2)))
-						break;
-					param2 = g_value_get_long(value2);
-					if (G_LIKELY (param2 >= 0 && param2 < 256)) {
-						if (param == 38) {
-							terminal->pvt->screen->defaults.attr.fore = param2;
-						} else {
-							terminal->pvt->screen->defaults.attr.back = param2;
-						}
+				}
+				if (G_LIKELY (color != -1)) {
+					if (param == 38) {
+						terminal->pvt->screen->defaults.attr.fore = color;
+					} else {
+						terminal->pvt->screen->defaults.attr.back = color;
 					}
-					i += 2;
-					break;
-				default:
-					break;
 				}
 			}
 			break;
